#!/usr/bin/python

# 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%?

from projecteuler import is_prime, timing


@timing
def p058() -> None:
    # Starting with 1, the next four numbers in the diagonal are 3 (1+2), 5 (1+2+2), 7 (1+2+2+2)
    # and 9 (1+2+2+2+2). Check which are prime, increment the counter every time a new prime is
    # found, and divide by the number of elements of the diagonal, which are increase by 4 at
    # every cycle. The next four number added to the diagonal are 13 (9+4), 17 (9+4+4), 21 and 25.
    # Then 25+6 etc., at every cycle the step is increased by 2. Continue until the ratio goes below 0.1.
    i = 1
    l = 1
    step = 2
    count = 0
    diag = 5

    while True:
        i = i + step

        if is_prime(i):
            count = count + 1

        i = i + step

        if is_prime(i):
            count = count + 1

        i = i + step

        if is_prime(i):
            count = count + 1

        i = i + step
        ratio = count / diag

        step = step + 2
        diag = diag + 4
        l = l + 2

        if ratio < 0.1:
            break

    print('Project Euler, Problem 58')
    print(f'Answer: {l}')


if __name__ == '__main__':
    p058()