프로젝트 오일러 35번

count_result=0
count_sosoo=0
def sieve(n):
    if n < 2:
        return []
    s = [0, 0] + [1] * (n - 1)
    for i in range(2, int(n**.5)+1):
        if s[i]:
            s[i*2::i] = [0] * ((n - i)//i)
    return [i for i, v in enumerate(s) if v]
arr=sieve(1000000)
arr_length=len(arr)
for i in range(0,arr_length):
    numberString=str(arr[i])
    numberString_length=len(numberString)
    for j in range(0,numberString_length-1):
        stringCircular=numberString[-(j+1):]+numberString[0:numberString_length-(j+1)]
        if((int)(stringCircular) in arr):
            count_sosoo=count_sosoo+1
        else:
            break
    if(count_sosoo==numberString_length-1):
        count_result=count_result+1
    count_sosoo=0 
print(count_result)
#반환 시간 : 94.5s

이전에 알고리즘 자체는 답이 나오게 만들어 놨는데

소수를 구하는 데 시간이 너무 오래 걸려서

'에라토스테네스의 체'를 사용하여 소수를 구하였다.

(출처 : http://codingdojang.com/scode/503)

먼저 소수를 구해서 리스트로 만들어놓은 다음

그 요소 하나하나를 이리저리 조작해서 순환수로 만든 후

그 순환수가 소수가 들어있는 리스트에 포함되어 있는지를 검사하여

답을 구하였다.