Project Euler Problem 58

Problem 58

05 December 2003

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Answer: 26241

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Problem58 {
        static bool isPrime(int value) {
            if (value <= 1) return false;
            for (int i = 2; i * i <= value; i++) {
                if (value % i == 0) return false;
            }
            return true;
        }

        public static void run() {
            var num = 1;
            var count = 1;
            var countPrime = 0;
            for (var inc = 2; ; inc += 2) {
                for (var i = 0; i < 4; i++) {
                    num += inc;
                    count++;
                    if (isPrime(num)) countPrime++;                   
                }
                if (countPrime * 10 < count) {
                    Console.WriteLine(inc + 1);
                    break;
                }
            }
        }
    }
}

 

Python

from math import sqrt

def isPrime(n):    

    for i in xrange(2, sqrt(n) + 1):

        if n % i == 0: return 0

    return 1

def problem58():

    num = 1

    count = 1

    countPrime = 0

    inc = 2

    while True:

        for _ in xrange(0, 4):

            num += inc

            count += 1

            if isPrime(num): countPrime += 1

        if countPrime * 10 < count:

            print inc + 1

            break

        inc += 2

    

problem58()