Project Euler Solution #35: Circular primes

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 number is divisible by 3 or 5, we know it can't be a prime and could use this as an early break, but since the lookup is \(O(1)\) and the loop stops immediately, we don't have a gain here. All these derivations 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;
}