Project Euler # 35 Circular primes in Python

Question

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?

Here's my implementation in Python 3. Awaiting feedback.

from time import time


def is_prime(number):
    """returns True for a prime number, False otherwise."""
    factor = 2
    while factor * factor <= number:
        if number % factor == 0:
            return False
        factor += 1
    return True


def circulate(number):
    """returns all circulations of a number."""
    for n in str(number):
        if not int(n) % 2:
            return False
    circulations = []
    digits = list(str(number))
    for i in range(len(str(number))):
        last = digits.pop()
        circulations.append(last + ''.join(digits))
        digits = [last] + digits
    return [int(x) for x in circulations]


def circular_primes(limit):
    """returns all circular primes below limit."""
    all_circulations = [2]
    for num in range(3, limit, 2):
        if is_prime(num):
            check = 0
            if circulate(num):
                circulations = circulate(num)
                for circulation in circulations:
                    if not is_prime(circulation):
                        check += 1
                if not check:
                    all_circulations.extend(circulations)
    return all_circulations


if __name__ == '__main__':
    start_time = time()
    print(len(set(circular_primes(200000))))
    print(f'Time: {time() - start_time} seconds.')

Answer 1

Let's start with a quick analysis of your current algorithm. For each number less than n (1000000 in your case) it does sqrt(n)log(n) operations (sqrt for is_prime*logcycles). However, some fairly simple things about this problem make it much easier to solve.

As you probably know, any 2 digit or greater number ending in 2,4,6,8 or 5 is not prime since it is divisible by 2 or 5. Thus when constructing circular primes, you don't even have to check numbers that have these digits in them (and add 2 to the result for 2,5)

Thus by changing the main bit of code to only generate reasonable candidates, you do significantly less work.

def digit_combinations(digit_list, n):
    if n == 1:
        for digit in digit_list:
            yield digit
        return
    for digit in digit_list:
        for part in digit_combinations(digit_list, n-1):
            yield digit + 10*part


def circular_primes(digits):
    if digits == 1:
        return 4 # 2,3,5,7

    all_circulations = [2,3,5,7]
    for i in range(2, digits):
        for num in digit_combinations((1,3,7,9), i):
            if is_prime(num):
                check = 0
                if circulate(num):
                    circulations = circulate(num)
                    for circulation in circulations:
                        if not is_prime(circulation):
                            check += 1
                    if not check:
                        all_circulations.extend(circulations)
    return all_circulations

By my timings, this code can return the 8 digit or less ones in 3 seconds, where yours took 7 seconds to do only up to 1 million.