# Project Euler 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 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; }