Project Euler 35

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?

문제:

소수 중 각 자릿수를 순환시켜도 모두 소수인 수를 써큘러 소수라 한다.(circular prime) 197은 소수이면서 각 자릿수를 순환시킨 971, 719도 소수이므로 써큘러 소수에 해당한다.

100보다 작은 써큘러 소수는 다음과 같이 13개가 있다: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97

백만보다 작은 써큘러 소수는 몇 개일까?

Solution:

from sympy import isprime,sieve
import time

def cirPrime(n): #Circular Prime 일 경우 True를 반환한다.
    numlist = list(str(n))
    # 숫자에 짝수가 들어간 경우를 제외시켜준다.
    if numlist.count('0') != 0:
        return False
    elif numlist.count('2') != 0:
        return False
    elif numlist.count('4') != 0:
        return False
    elif numlist.count('6') != 0:
        return False
    elif numlist.count('8') != 0:
        return False
    
    for i in range(len(str(n))):
        if not isprime(int("".join(numlist))):
            return False
        numlist.append(numlist.pop(0)) #처음 수를 뒤로 옮긴다.
    return True

cir = [2]
start = time.time()
for i in sieve.primerange(1,1000000):
    if cirPrime(i):
        cir.append(i)

print("""The number of circular primes below one million: {0}
Found in ... {1:.3f}s""".format(len(cir),time.time() - start))

2 는 cirPrime 에 들어가면 False 를 반환시키므로 미리 list 에 추가시켜준다.

0.62 초 걸렸다!

55