Robert Eisele
Engineer, Systems Architect and DBA

Project Euler 35: Circular primes

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?

Solution

With Problem 10 I introduced a prime sieve, which can be used for this question again. After that we can walk through the sieve (skipping even numbers) and if a number is prime, we check if all rotations are prime, which leads to the following implementation:

var NOT_PRIME = null;
function solution(limit) {

// Below 100
var num = 13;

NOT_PRIME = sieve(limit);

for (var i = 101; i < limit; i+= 2) {

if (!NOT_PRIME[i] && allRotationsPrime(i))
num++;
}
return num;
}
solution(1000000);

The remaing question is, how can we rotate through the digits? A naive implementation would use strings like so:

function allRotationsPrime(n) {
var num = String(n);

for (var i = 1; i < num.length; i++) {

num = num.slice(-1) + num.slice(0, num.length - 1)
if (NOT_PRIME[parseInt(num, 10)]) {
return false;
}
}
return true;
}

However, we can do a lot better. With Problem 25, I've proved that the length $$L(n)$$ of a number $$n$$ is

$L(n) = \lfloor 1+\log_{10}(n)\rfloor$

Cutting off the last digit of a natural number can be done by

$r_1(n) = \left\lfloor\frac{n}{10}\right\rfloor = \frac{n - (n \bmod 10)}{10}$

Shifting the cut-off digit to the left is as simple as:

$r_2(n) = 10^{L(n) - 1}(n \bmod 10)$

Therefore, we can rotate a number quite easily with:

$\begin{array}{rl}r(n) &= r_1(n) + r_2(n)\\&= \frac{n - (n \bmod 10)}{10} + 10^{L(n) - 1} \cdot (n \bmod 10)\\&= \frac{n - (n \bmod 10)}{10} + \frac{10^{L(n)}}{10} \cdot (n \bmod 10)\\&= \frac{n + (10^{L(n)} - 1) \cdot (n \bmod 10))}{10}\end{array}$

We could do another optimization. If the last digit is a 2 or a 5, we know it can't be a prime and could use this as an optimization, but since the lookup is $$O(1)$$, it doesn't matter. All this information packed together results in the following implementation:

function allRotationsPrime(n) {

var l = Math.floor(Math.log10(n)) + 1;
var p = Math.pow(10, l) - 1;

for (var i = 1; i < l; i++) {
n = (n + n % 10 * p) / 10;
if (NOT_PRIME[n]) {
return false;
}
}
return true;
}

« Back to problem overview