Project Euler 35

• 問題

Problem 35：Circular primes
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 sieveEratosthenes(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    primes = []
    for i in range(2, (num + 1)):
        if isPrime[i]:
            primes.append(i)
            for j in range(2 * i, (num + 1), i):
                isPrime[j] = False
    return primes

def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

prime = sieveEratosthenes(999999)
circularPrime = []

for n in prime:
    temp = list(str(n))
    l = len(temp)
    isCircularPrime = True
    for i in range(l - 1):
        tempChar = temp.pop(0)
        temp.append(tempChar)
        tempNum = int("".join(temp))
        if not isPrime(tempNum):
            isCircularPrime = False
            break
    
    if isCircularPrime:
        circularPrime.append(n)

print(len(circularPrime))