from primefac import isprime, primes
from itertools import product  # cartesian product

'''
Circular primes
Project Euler: Problem 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?
'''


def lst_2_int(lst):
    return int(''.join(map(str, lst)))


def is_circular(p):
    return all(isprime(lst_2_int(p[i:]+p[:i])) for i in range(len(p)))


def is_circular_2(p):
    for i in range(len(p)):
        if not isprime(int(''.join(map(str, p[i:]+p[:i])))):
            return False
    return True


def repunit(k):
    return (10**k-1)//9


def find_circular_primes_under(digits):
    # Finds all circular primes under 10^digits
    if type(digits) != int or digits <= 0:
        raise ValueError(
            "Error: power needs to be a positive integer, 10^input")

    circular_lst = []
    # Circular primes under 10
    total = 0
    for k in xrange(10):
        if isprime(k):
            circular_lst.append(k)

    # Circular primes under 10^6
    for k in xrange(2, min(digits+1, 7)):
        for combo in product([1, 3, 7, 9], repeat=k):
            if is_circular_2(list(combo)):
                circular_lst.append(''.join(map(str, combo)))

    # All circular primes over 10^6 are repunit primes (1...1 where ... =
    # index)
    if digits > 6:
        prime_lst = primes(digits+1)
        # All repunit primes have a prime number of digits
        for prim in prime_lst[3::]:
            if isprime(repunit(prim)):
                circular_lst.append('1 ... 1 ['+str(prim)+']')
    return circular_lst

if __name__ == '__main__':

    circular_primes = find_circular_primes_under(1050)
    for prim in circular_primes:
        print prim
    print "Found a total of", len(circular_primes), 'circular primes.'

from primefac import isprime, primes
from itertools import product  # cartesian product

'''
Circular primes
Project Euler: Problem 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?
'''


def lst_2_int(lst):
    return int(''.join(map(str, lst)))


def is_circular(p):
    return all(isprime(lst_2_int(p[i:]+p[:i])) for i in range(len(p)))


def is_circular_2(p):
    for i in range(len(p)):
        if not isprime(lst_2_int(p[i:]+p[:i])):
            return False
    return True


def repunit(k):
    return (10**k-1)//9


def find_circular_primes_under(digits):

    if type(digits) != int or digits <= 0:
        raise ValueError(
            "Error: power needs to be a positive integer, 10^input")

    circular_lst = []
    # Circular primes under 10
    total = 0
    for k in xrange(10):
        if isprime(k):
            circular_lst.append(k)

    # Circular primes under 10^6
    for k in xrange(2, min(digits+1, 7)):
        for combo in product([1, 3, 7, 9], repeat=k):
            if is_circular_2(list(combo)):
                circular_lst.append(lst_2_int(combo))

    # All circular primes over 10^6 are repunit primes (1...1 where ... =
    # index)
    if digits > 6:
        prime_lst = primes(digits+1)
        # All repunit primes have a prime number of digits
        for prim in prime_lst[3::]:
            if isprime(repunit(prim)):
                circular_lst.append('1 ... 1 ['+str(prim)+']')
    return circular_lst

if __name__ == '__main__':

    circular_primes = find_circular_primes_under(400)
    for prim in circular_primes:
        print prim
    print "Found a total of", len(circular_primes), 'circular primes.'

Circular primes

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

I solved this question some time ago, and have now come back to it because I saw it pop up a few times here on CR. I wanted to over-engineer the problem and instead of finding the cyclic primes under a million I wanted to find them under some crazy big number.

It is not terribly quick, but uses that all cyclic primes above a million are repunit primes with a prime number of digits.

I included two different ways of checking whether a number (or in this case a list of numbers) is a cyclic prime. I use the following

However after some quick googling, the following seem to be the "prefered" way

However after some light speedtests using timeit, this version is a tad slower. Looking for any sort of comments on my code. Not sure if it can be improved speedwise, but comments there are appreciated as well.

from primefac import isprime, primes
from itertools import product  # cartesian product

'''
Circular primes
Project Euler: Problem 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?
'''


def lst_2_int(lst):
    return int(''.join(map(str, lst)))


def is_circular(p):
    return all(isprime(lst_2_int(p[i:]+p[:i])) for i in range(len(p)))


def is_circular_2(p):
    for i in range(len(p)):
        if not isprime(int(''.join(map(str, p[i:]+p[:i])))):
            return False
    return True


def repunit(k):
    return (10**k-1)//9


def find_circular_primes_under(digits):

    if type(digits) != int or digits <= 0:
        raise ValueError(
            "Error: power needs to be a positive integer, 10^input")

    circular_lst = []
    # Circular primes under 10
    total = 0
    for k in xrange(10):
        if isprime(k):
            circular_lst.append(k)

    # Circular primes under 10^6
    for k in xrange(2, min(digits+1, 7)):
        for combo in product([1, 3, 7, 9], repeat=k):
            if is_circular_2(list(combo)):
                circular_lst.append(''.join(map(str, combo)))

    # All circular primes over 10^6 are repunit primes (1...1 where ... =
    # index)
    if digits > 6:
        prime_lst = primes(digits+1)
        # All repunit primes have a prime number of digits
        for prim in prime_lst[3::]:
            if isprime(repunit(prim)):
                circular_lst.append('1 ... 1 ['+str(prim)+']')
    return circular_lst

if __name__ == '__main__':

    circular_primes = find_circular_primes_under(1050)
    for prim in circular_primes:
        print prim
    print "Found a total of", len(circular_primes), 'circular primes.'

The problem

Circular primes

Problem 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?

My attempt

I solved this question some time ago, and have now come back to it because I saw it pop up a few times here on CR. I wanted to over-engineer the problem and instead of finding the circular primes under a million I wanted to find them under some crazy big number.

It is not terribly quick, but uses that all circular primes above a million are repunit primes with a prime number of digits.

I included two different ways of checking whether a number (or in this case a list of numbers) is a circular prime. I use the following

However after some quick googling, the following seem to be the "preferred" way

However after some light speedtests using timeit, this version is a tad slower. As many other answers do I cycle through the products of the odd integers [1, 3, 7, 9] since no prime can end in an even integer, or 5.

I do not bother saving the primes or non primes already found. Is it "worth" it? isprime from the primefac libary already seems quite fast. To find the really big circular primes I iterate over the repunit primes. Eg primes only consisting of 1`s. No need to check if it is circular. I also used the small increase that a repunit number is prime if and only if it contains a prime number of digits.

Looking for any sort of general comments on my code. Not sure if my code can be improved speedwise, but comments there are appreciated as well.

The code

from primefac import isprime, primes
from itertools import product  # cartesian product

'''
Circular primes
Project Euler: Problem 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?
'''


def lst_2_int(lst):
    return int(''.join(map(str, lst)))


def is_circular(p):
    return all(isprime(lst_2_int(p[i:]+p[:i])) for i in range(len(p)))


def is_circular_2(p):
    for i in range(len(p)):
        if not isprime(int(''.join(map(str, p[i:]+p[:i])))):
            return False
    return True


def repunit(k):
    return (10**k-1)//9


def find_circular_primes_under(digits):
    # Finds all circular primes under 10^digits
    if type(digits) != int or digits <= 0:
        raise ValueError(
            "Error: power needs to be a positive integer, 10^input")

    circular_lst = []
    # Circular primes under 10
    total = 0
    for k in xrange(10):
        if isprime(k):
            circular_lst.append(k)

    # Circular primes under 10^6
    for k in xrange(2, min(digits+1, 7)):
        for combo in product([1, 3, 7, 9], repeat=k):
            if is_circular_2(list(combo)):
                circular_lst.append(''.join(map(str, combo)))

    # All circular primes over 10^6 are repunit primes (1...1 where ... =
    # index)
    if digits > 6:
        prime_lst = primes(digits+1)
        # All repunit primes have a prime number of digits
        for prim in prime_lst[3::]:
            if isprime(repunit(prim)):
                circular_lst.append('1 ... 1 ['+str(prim)+']')
    return circular_lst

if __name__ == '__main__':

    circular_primes = find_circular_primes_under(1050)
    for prim in circular_primes:
        print prim
    print "Found a total of", len(circular_primes), 'circular primes.'