Project Euler Problem 35 Solution

Project Euler Problem 35 Solution

Circular primes

by {BetaProjects} | Project Euler & HackerRank

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?


Project Euler 35: Circular primes

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 R5 = 11111. Some of these circular-repunit primes include R19, R23, R317, R1031, R49081, and on from there.

HackerRank version

HackerRank Project Euler 35 wants us to find the sum of the circular primes below 10 ≤ N ≤ 106 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))

Last Word

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