Solution for Project Euler problem 58 in 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 05 04 03 12 29
40 19 06 01 02 11 28
41 20 07 08 09 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%?
Readme.me - details about project
start.py - code to solve the problem proposed in the description.
Starting with number 1, for each new square arond it, we have 4 new odd numbers on each vertex of this square.
Again, starting with number 1, we can find the next vertex adding 2, thus, therefore the 4 vertices will be 3,5,7,9.
We check for each vertex if it's prime and keep track of the amount of primes.
Once we complete the square, the next square will have a side length equal to the side length of the previous square plus 2,
that is the ammount of numbers between one vertex and the next.
so to find the next vertex, instead of adding 2, we will have to add 4 (2+2),
again, 4 will be the amount of numbers between vertices in this new square.
For the next square we will be adding 6 (4+2), and so on.
We repeat all this process until the ratio prime/odds is below 10% (or 0.1).
This solution find the answer in less than a second.