[Project Euler: 35][1] is stated in the following way

> 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

    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

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

    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)))

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.'

  [1]: https://projecteuler.net/problem=35