Project Euler Problem 35 Solution: Circular primes

Project Euler Problem 35 Statement

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

While researching circular primes (not to be confused with permutable primes) it became clear that the only interesting ones are below one million. After one million the only circular primes are repunits.

Repunits are numbers composed of only 1s, and is described as R₅ = 11111. Some of these circular-repunit primes include R₁₉, R₂₃, R₃₁₇, R₁₀₃₁, R₄₉₀₈₁, and on from there.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 35

HackerRank Project Euler 35 wants us to find the sum of the circular primes below 10 ≤ N ≤ 10⁶ instead of a count. The same algorithm solves both requirements. The program listed here prints the count, the circular primes and their sum.

Python Source Code

def prime_sieve(n):
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
def rotate(s):
    return [s[n:] + s[:n] for n in range(1, len(s))]

s = set('024568')
L = int(input("Enter a search limit less than 1,000,000? "))
primes = set(['2','5']+[p for p in map(str, prime_sieve(L)) if not set(p).intersection(s)])
circular_primes = [int(p) for p in primes if all(pr in primes for pr in rotate(p))]

print ("Number of circular primes below", L, " is",len(circular_primes))
print ("They are:", sorted(circular_primes), " With a sum of",sum(circular_primes))

Run Project Euler Problem 35 using Python on repl.it.

Last Word

Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A068652: Numbers such that every cyclic permutation is a prime.