Duncan's blog

October 22, 2014

Project Euler: problem 35 (PHP) – Circular primes

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

Punch meI ignored this Project Euler puzzle first time round I tried doing them, 5-6 years ago, with ColdFusion and Python.  Looking at it again recently I thought I could tackle it with PHP.  I’m doing these  as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 35:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

It took me a little while to get close to the answer, and I know this code isn’t the most efficient, but it works:

<?php
require 'isPrime.php';

$primes = [2 => 1];
$limit = 1000000;
$circulars = 1;
$arrCirculars = array('2' => true);

function getExcludedDigits($value) {
	return $value % 2 == 0 && $value != 5;
}

for ($i = 3; $i < $limit; $i+=2) {
	$isCircular = false;
	$rotatedDigits = str_split($i);
	
	if (count(array_filter($rotatedDigits, 'getExcludedDigits')) == 0) {
		for ($j = 1; $j <= strlen($i); $j++) {
			array_push($rotatedDigits, array_shift($rotatedDigits));
			$rotatedNumber = implode($rotatedDigits);

			// if this number's already in our primes[], move onto the next iteration
			if (array_key_exists($rotatedNumber, $primes)) {
				continue;
			}
			
			if (!isPrime($rotatedNumber)) {
				$isCircular = false;
				break;
			}
			
			$isCircular = true;
			$primes[$rotatedNumber] = true;
		}
		
		if ($isCircular) {
			if (substr_count($rotatedNumber, substr($rotatedNumber, 0, 1)) == strlen($rotatedNumber)) {
				$circulars++;
			} else {
				$circulars += strlen($rotatedNumber);
			}
			$arrCirculars[$i] = true;	
		}
	}
}

echo $circulars;

Re-using my isPrime function from puzzle 3.

One thing you’ll quickly realise is that we don’t have to calculate if every number is prime.  For instance early on in the loop you get 1951, which is a prime number.  Shifting the first number off there and sticking it on the end, you get 9511, which is also prime.  And doing it again, you get 5119, which is prime too.  However on its fourth iteration you have 1195, which is divisible by 5 and therefore not prime.  However rather than calculate if any of those four rotations of those digits would be prime, you can save time by excluding it as soon as you see there’s a 5 in there.  Similarly with numbers containing any even digits.

During the loop, I store every prime number to an array.  If it’s already in the array, then I know I don’t need to do it again.

At the end of the inner for loop, I increment my counter by the length of the number I’ve currently been looking at.  e.g. if I was on 197, which is prime, and its rotations 971 and 719 are also prime, I simply increment by 3.  I make a special exception for numbers like 11 where all the digits are the same, to make sure I don’t double-count it.

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

Blog at WordPress.com.

%d bloggers like this: