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
    return total
end

@time circularprimes(1_000_000)

> 0.127895 seconds (1.55 M allocations: 155.575 MiB, 9.90% gc time)
>
>  55