I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code

Problem 46:

*It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.*

*9 = 7 + 2×1*^{2}

* 15 = 7 + 2×2*^{2}

* 21 = 3 + 2×3*^{2}

* 25 = 7 + 2×3*^{2}

* 27 = 19 + 2×2*^{2}

* 33 = 31 + 2×1*^{2}

*It turns out that the conjecture was false.*

*What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?*

This was another of those problems that I’d initially passed over, having decided it looked a bit tricky. Then looking at it again realised it probably wasn’t too difficult. And I turned out to be right!

A composite number is basically any positive integer that isn’t a prime number.

My logic is simply:

- Loop through odd numbers, from 3 upwards.
- For each number, if it’s prime, add it to an array of primes for later reference.
- If it’s not prime, work out if it matches the conjecture:
- Subtract the next largest prime, then examine the remainder
- Divide the remainder by 2. if it’s a square number then we’re meeting the conjecture. Move onto the next odd number.
- Otherwise keep subtracting the primes, checking the remainders.
- If we’ve looped through all the primes then we must have reached a number that doesn’t meet the conjecture.

This runs in about 40ms:

<?php
$primes = [2];
$i= 1;
while (true) {
$i+= 2;
if (isPrime($i)) {
$primes[] = $i;
} else {
for($j = count($primes)-1; $j > 0; $j--) {
$remainder = $i - $primes[$j];
$remainder = $remainder / 2;
$root = sqrt($remainder);
if ((int) $root == $root) {
continue 2;
}
}
echo $i;
break;
}
}
function isPrime($x)
{
$root = sqrt($x);
for ($i = 3; $i <= $root; $i += 2) {
if ($x % $i == 0) {
return false;
}
}
return true;
}

I’m using a modified version of my original isPrime function, just because I know I don’t need to check for even numbers.

The loop backwards through the primes was maybe a bit of overkill; using a simple foreach loop through the primes in ascending order took more like 100ms.

What else… I check if a square root is the same as when it’s cast to an integer (not sure this is the best approach). Then use *continue 2;* to get out of our inner-most loop and move onto the next value in our parent loop.

### Like this:

Like Loading...

*Related*

You could possibly expedite this by optimising your prime look-up. You don’t need to check whether the number is divisible by every odd number, you only need to check if they’re divisible by other primes. This does require maintaining the list of previously discovered primes though, but this is probably OK in this context as you seem to be counting up anyhow (I did not look at the entirety of the logic). Or I did write that prime generator thing a while back… you could pinch that if you wanted to… http://blog.adamcameron.me/2014/09/php-another-generator-example-primes.html

—

Adam

Comment by dacameron — December 19, 2014 @ 12:17 am |

ah ok, good call. It probably won’t make much difference here, but that could be useful for some of the other Euler puzzles where you’re looping over primes into the millions

Comment by duncan — December 19, 2014 @ 9:10 am |