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 49It 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%?
This problem has some similarities to problem 28. In that case the spiral went clockwise; this one it goes anti-clockwise. For our purposes that’s a red herring.
We want to loop round, calculating the value for the corners of our spiral.
For each value, work out if it is prime (re-using the IsPrime function I first used back in problem 3).
Keep count of how many primes there are.
Also keep track of how long the side of our spiral is.
At each loop round the spiral, check if the ratio of primes / length is less than 10%.
<cfset numPrimes = 0>
<cfset length = 1>
<cfset number = 1>
<cfset increment = 2>
<cfset ratio = 100>
<cfloop condition="ratio GT 10">
<cfset length += 2>
<!--- add our increment 4 times, calculating each time if it's prime --->
<cfloop index="i" from="1" to="4">
<cfset number += increment>
<!--- the 4th corner is never prime --->
<cfif i LT 4 AND IsPrime(number)>
<cfset numPrimes++>
</cfif>
</cfloop>
<cfset ratio = numPrimes / ((2*length)-1) * 100>
<cfset increment += 2>
</cfloop>
<cfoutput>#length#</cfoutput>
<cfscript>
function isPrime(x)
{
var isPrime = true;
var i = 0;
if (x LT 2)
{
return false;
}
if ((NOT x MOD 2) AND (x GT 2))
{ // a multiple of 2, but not 2 itself
return false;
}
for (i = 3; i LTE SQR(x); i = i + 2)
{
if (NOT x MOD i)
{ // found a factor of x
return false;
}
}
return isPrime;
}
</cfscript>
Like in problem 28, we can see the corner values go:
3, 5, 7, 9, [increment: 2]
13, 17, 21, 25, [increment: 4]
31, 37, 43, 49 [increment: 6]
etc.
So we can work out the corner values by starting at 1, adding 2 to our increment each time round the spiral, then adding the increment four times to calculate the corners.
We don’t need to work out if the 4th corner is prime; it will always be a square number. e.g. on spiral with length 3, the 4th corner is 32 = 9. On length 5, the 4th corner is 52 = 25, and so on. So the if statement <cfif i LT 4 AND IsPrime(number)> will only execute the IsPrime() function if i LT 4 evaluates to true.
