// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (18 votes, average: 4.78 out of 5)
Loading...

Project Euler Solutions

Project Euler 35 Solution

Project Euler 35 Solution

Project Euler 35: Find the number of circular primes below one million


Project Euler 35 Problem Description

Project Euler 35: 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?

Analysis

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 circular primes are only repunits (a number composed of just 1s, such as R11 = 11111111111) with many digits. The only circular primes after one million are repunit primes: R19, R23, R317, R1031, R49081, and on from there.

To solve this problem we generate a set of prime numbers below 1 million (78,498 primes) using our prime sieve and excluded those that contained the digits {0, 2, 4, 5, 6 or 8} (except primes 2 and 5) because as the prime is rotated it cannot end with any of these digits and still remain prime. That leaves 1,113 prime candidates to investigate.

We have a variable s predefined as a set {0,2,4,5,6,8} so we can check the intersection with the stringified version of the prime number candidate. If there is no intersection the prime is added to the set primes.

primes = set(['2','5']+[str(p) for p in prime_sieve(L) if not set(str(p)).intersection(s)])

The set primes also serves as a de facto ‘is prime()’ function. If a particular element exists in the set then the number is prime and if it does not, then it’s composite.

As we consider each qualified prime, the all() function returns True if all the rotations are a member of the primes set and, therefore, a circular prime number.

circular_primes = [p for p in primes if all(pr in primes for pr in rotate(p))]

This solution handles the HackerRank Project Euler 35 problem as well. In fact, we collect circular prime values as HackerRank requests a sum of circular primes below some limit less than one million and Project Euler only requires a count.

Project Euler 35
This program and method
solves all test cases for
Project Euler 35 on HackerRank

Project Euler 35 Solution

Runs < 0.125 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 35 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|55|

Afterthoughts

Project Euler 35 Solution last updated

Discussion

3 Responses to “Project Euler 35 Solution”

  1. About 4s in python:

    from Euler import prime_sieve, is_prime
    
    def circular (n):
        circ = []
        n = str(n)
        for i in range(len(n)):
            circ.append(int(n[1:]+n[0]))
            n = n[1:]+n[0]
        return circ
    
    def is_prime_list (List):
        for i in List:
            if not is_prime(i):
                return False
        return True
    
    
    primes = prime_sieve(1000000)
    circ = []
    for i in primes:
        if (is_prime_list(circular(i))):
            circ.append(i)
        
    print "Answer to PE35 = " + str(len(circ))
    

    Posted by Murilo Camargos | January 27, 2013, 2:53 PM
  2. Great explanation! Thank you.

    Posted by Tarren | April 9, 2009, 3:36 AM

Post a comment