Duncan's blog

December 13, 2009

Project Euler problem 58

Filed under: Coldfusion,Project Euler — duncan @ 9:00 am
Tags: , , ,

Problem 58:

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

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.

1 Comment »

  1. […] previously blogged about this Project Euler puzzle over 5 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler problem 58 (PHP) – Spiral primes | Duncan's blog — October 21, 2014 @ 8:01 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: