project euler problem 58 https projecteuler netproblem58 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 813 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 solution we have to find an odd length side for which square falls below 10 with every layer we add 4 elements are being added to the diagonals lets say we have a square spiral of odd length with side length j then if we move from j to j2 we are adding jjj1 jj2j1 jj3j1 jj4j1 out of these 4 only the first three can become prime because last one reduces to j2j2 so we check individually each one of these before incrementing our count of current primes checks to see if a number is a prime in osqrtn a number is prime if it has exactly two factors 1 and itself isprime0 false isprime1 false isprime2 true isprime3 true isprime27 false isprime87 false isprime563 true isprime2999 true isprime67483 false 2 and 3 are primes negatives 0 1 all even numbers all multiples of 3 are not primes all primes number are in format of 6k 1 returns the side length of the square spiral of odd length greater than 1 for which the ratio of primes along both diagonals first falls below the given ratio solution 5 11 solution 2 309 solution 111 11317 checks to see if a number is a prime in o sqrt n a number is prime if it has exactly two factors 1 and itself is_prime 0 false is_prime 1 false is_prime 2 true is_prime 3 true is_prime 27 false is_prime 87 false is_prime 563 true is_prime 2999 true is_prime 67483 false 2 and 3 are primes negatives 0 1 all even numbers all multiples of 3 are not primes all primes number are in format of 6k 1 returns the side length of the square spiral of odd length greater than 1 for which the ratio of primes along both diagonals first falls below the given ratio solution 5 11 solution 2 309 solution 111 11317
import math


def is_prime(number: int) -> bool:
    

    if 1 < number < 4:
        
        return True
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
        
        return False

    
    for i in range(5, int(math.sqrt(number) + 1), 6):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True


def solution(ratio: float = 0.1) -> int:
    

    j = 3
    primes = 3

    while primes / (2 * j - 1) >= ratio:
        for i in range(j * j + j + 1, (j + 2) * (j + 2), j + 1):
            primes += is_prime(i)
        j += 2
    return j


if __name__ == "__main__":
    import doctest

    doctest.testmod()