프로젝트 오일러 37번

import math
def isPrime(n):
    if(n==1):
        return False
    count=0
    for i in range(2,(int)(math.sqrt(n))+1):
        if(n%i==0):
            count=count+1
    if(count==0):
        return True
    else:
        return False
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]
sum=0
count=0
arr=sieve(1000000)
arr.remove(2)
arr.remove(3)
arr.remove(5)
arr.remove(7)
for i in range(0,len(arr)): 
    number=(str)(arr[i]) 
    number_left=number
    number_right=number
    length=len(number)
    length_left=length
    length_right=length
    judgement_left=False
    judgement_right=False
    for j in range(0,length-1):
        number_left=number_left[1:]
        if(isPrime((int)(number_left))):
            judgement_left=True
        else:
            judgement_left=False
            break
    for j in range(0,length-1):
        length_right=length_right-1
        number_right=number_right[0:length_right]
        if(isPrime((int)(number_right))):
            judgement_right=True
        else:
            judgement_right=False
            break
    if(judgement_left and judgement_right):
        sum=sum+(int)(number)
        count=count+1
    if(count==11):
        break
print(sum)
#반환 시간 : 2.1s

오랫동안 헤맨 2페이지의 세 번째 문제이다.

이것 또한 이전에 알고리즘은 맞게 짜 놓은 것 같았는데

11번째의 조건에 맞는 수가 빠르게 나오지 않아서 일단 넘겼었다.

이전에 제곱근을 이용하여 약수를 빠르게 찾았고, 이를 활용하여 소수 판정 또한 빠르게 할 수 있어서

이번에는 정답을 보겠구나 싶었다.

isPrime()은 소수를 판정하는 함수이고, sieve()는 에라토스테네스의 체를 이용한 소수 찾기 함수이다.

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

일단 백만 까지의 모든 소수를 리스트 안에 저장하고, 2, 3, 5, 7은 제외했다.

리스트 각 요소에 접근하여 왼쪽에서부터 한 자리씩 없어지는 경우와 오른쪽에서부터 한 자리씩 없어지는 경우를 각각 만들어

소수 판정 함수를 통해 소수이면 True, 소수가 아니면 False를 반환하게 하였고

각각의 경우에 대해 모두 True이면 맞는 경우이므로 수를 세고 합계를 내었다.

문제에서 이런 조건에 맞는 수는 11개라고 하였으므로

11번째의 조건에 맞는 수를 구했을 때 작업을 종료하도록 하였다.