Duncan's blog

October 21, 2014

Project Euler problem 58 (PHP) – Spiral primes

Filed under: PHP,Project Euler — duncan @ 8:00 am

AmmoniteI 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 I’d appreciate any feedback on my PHP code.

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

Code:

<?php
require 'isPrime.php';

$numPrimes = 0;
$spiralLength = 1;
$number = 1;
$increment = 2;
$ratio = 100;

while ($ratio > 10) {
	$spiralLength += 2;

	// add our increment 4 times, calculating each time if it's prime
	for ($corner = 1; $corner <= 4; $corner++) {
		$number += $increment;

		// the 4th corner is never prime
		if ($corner < 4 && isPrime($number)) {
			$numPrimes++;
		}
	}
	
	$ratio = $numPrimes / ((2 * $spiralLength) - 1) * 100;
	
	$increment += 2;
}

echo $spiralLength;

Re-using the isPrime function from Problem 3.

Looping until we fall beneath a 10% ratio, adding up the numbers of primes along the corners of the spiral and calculating that amount as a ratio of the current length of the spiral’s side.

Advertisements

Leave a Comment »

No comments yet.

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

Create a free website or blog at WordPress.com.

%d bloggers like this: