[PE] Project Euler 37

프로젝트 오일러 37번도 나이브하게 덤볐는데도 풀린 문제. 이 문제는 어떤 숫자 p가 주어졌을때, 이 숫자 자체도 소수이면서 좌측부터 숫자를 하나씩 제거하면서 만드는 숫자들도 전부 소수, 우측부터 숫자를 하나씩 제거하면서 만드는 숫자들도 전부 소수인 숫자를 truncatable prime이라고 정의하고, 딱 11개 존재하는 이 숫자들을 전부 찾아서 더하라는 문제다.

 

별 다른 테크닉 없이 10부터 시작하여 1씩 더해가면서 해당 숫자가 조건을 만족하면 리스트에 더하는 루프를 돌고, 리스트 크기가 11이 되면 루프를 빠져나오는 식으로 구현했다.

def p_test(n):
    if n<2: return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0: return False
    return True
 
def tp_test(n):
    nn = str(n)
    for i in range(len(nn)):
        if not p_test(int(nn[i:])):
            return False
        if not p_test(int(nn[:i+1])):
            return False
    return True
 
l = []
x = 10
while len(l)<11:
    if tp_test(x): 
        print(x)
        l.append(x)
    x+=1
 
print(sum(l))

이렇게 짜도 10초 미만에 답을 구할 수 있다.