This problem is somewhat similar to Problem 28, except that this time we are checking the diagonals for prime numbers. We need to find the length of the side of the square for which the ratio of primes to composites on the diagonals falls below 10%.
I thought about trying to solve this in the same way as Problem 28, by building a array with a very large spiral and then working out from the centre until the required condition is reached. However, in a rare moment of self respect I chose to give the situation a little more thought. It turns out that this was a very good idea because building an array large enough isn't really workable.
If we ignore the spiral pattern we just have a long sequence of integers starting from 1. The numbers on the diagonals appear in a regular pattern.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37...
The numbers in red are the ones that are on the diagonals. There are four for each complete spiral. Initially, we add 2 to find the next corner, then 4, then 6 and so on forever. Some of the numbers in red are prime. The ratio of primes to composites gets smaller as we add more spirals. How many spirals must we add until less than 10% of the red numbers are prime?
Generating the red numbers is easy. Testing their primality takes time. When you have a hammer, every problem looks like a nail. My hammer is the sieve of Eratosthenese. At first I just generated the first 50,000 primes, put them in a set and then checked to see if any of the red numbers were in that set. It turns out that this doesn't work because we end up having to check numbers that are very much greater than 50,000. Instead, I used trial division with my set of primes to get the answer.