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
return total
end
@time circularprimes(1_000_000)
> 0.127895 seconds (1.55 M allocations: 155.575 MiB, 9.90% gc time)
>
> 55