프로젝트 오일러 37번 문제 - 잘려진 소수(truncatable prime)

어떤 한 수가 소수이고, 그수를 왼쪽 끝에서 한자리씩 잘라도 계속 소수인 수를 Truncatable prime 으로 정의 하기로 합니다. 예를 들면, 3797 는 소수이고, 오른쪽에서 한자리씩 자른수 379,  37, 3 세 수 모두 소수인 거죠.

이런 수를 11개 찾은후 합을 구하는 것이 문제입니다.(2,3,5,7 은 제외, 즉 두자리 이상의 소수부터 시작)

 

소수확인

def is_prime(num):
    if num==1 or num==0:
        return False
    loop=pow(num,0.5)
    i=2
    while i<=loop:
        if num%i==0:
            return False
        i+=1
    return True

number=100
while number<200:
    if is_prime(number):
        print(number, "prime")
    number+=1

101 prime
103 prime
107 prime
109 prime
113 prime
127 prime
131 prime
137 prime
139 prime
149 prime
151 prime
157 prime
163 prime
167 prime
173 prime
179 prime
181 prime
191 prime
193 prime
197 prime
199 prime

 

숫자 slice 하기

number=10
while number<200:
    string=str(number)
    for i in range(1,len(string)):
        print(string,string[:i],string[i:])
    number+=1

10 1 0
11 1 1
12 1 2
13 1 3
14 1 4
15 1 5
...
...

 

최종 Code

import time
start_time = time.time()

def is_prime(num):
    if num==1 or num==0:
        return False
    loop=pow(num,0.5)
    i=2
    while i<=loop:
        if num%i==0:
            return False
        i+=1
    return True

def is_truncatable_prime(num):
    string = str(num)
    for i in range(1,len(string)):
        if not ( is_prime(int(string[:i])) and is_prime(int(string[i:])) ):
            return False
    return True

number=10;count=0;total=0
while number<1000000:
    if is_prime(number) and is_truncatable_prime(number):
        count+=1;total+=number
        print(number,count)
    if count==11:
        break
    number+=1
print(total)

print("calculation time:",time.time()-start_time)

23 1
37 2
53 3
73 4
313 5
317 6
373 7
797 8
3137 9
3797 10
739397 11
748317
calculation time: 20.21382164955139