Circular Primes (PE35)

Circular Primes, problem 35 on Project Euler, asks us to find the number of circular primes under one-million.

A circular prime is defined as a number where all rotations of the digits are also prime. More concretely, for a prime, $$p$$, where,

$p = c_0 + c_1 \cdot 10 + \cdots + c_{n-1} \cdot 10^{n-1} + c_n \cdot 10^n\,,$

all permutations of the digit coefficients, $$c_i$$, should also be prime. The number $$197$$ is considered a circular prime because $$197$$, $$971$$, and $$719$$ are all prime. Notice how we are not talking about permutations because $$917$$ is not prime, but as specified, rotations. Therefore $$abc$$, $$bca$$, $$cab$$.

using Primes

function countdigits(x::Integer)
digit_len = 1
k = 10
while x % k != x
digit_len += 1
k *= 10
end
digit_len
end

function rotate(n::Integer)
len = countdigits(n)
rots = zeros(Int, len)
rots[1] = n

for k in 1:len-1
(p1, p2) = (fld(rots[k], 10^(len-1)),
mod(rots[k], 10^(len-1)))
rots[k+1] = p1 + p2 * 10
end

return rots
end

function circularprimes(N::Integer)
total = zero(Int)
checked = zeros(Int, N)
for k in 1:N
if checked[k] == one(Int)
continue
end

rseq = unique(rotate(k))
foreach(m -> checked[m] = one(Int), rseq)

if all(isprime, rseq)
total += length(rseq)
end
end
>  55