[PE] Project Euler 41

프로젝트 오일러 41번은 어떤 소수 n이 x자리 수일때, 1부터 x까지의 숫자가 모두 등장하면 이를 pandigital prime이라고 부른다고 한다면, 이러한 조건을 만족하는 제일 큰 소수 p를 구하라는 문제다.

 

pandigital 조건이 붙어있으므로 p는 아무리 커도 9자리여야 하는데, 1~9가 모두 등장하는 9자리 수는 각 자릿수를 다 더하면 45이므로 3의 배수가 되어 소수가 될 수 없다. 즉, p는 아무리 커봐야 8자리인 것이다.

 

문제에 나이브하게 접근하여 8자리 소수들을 전부 구한 뒤, 큰 소수부터 시작하여 위의 조건을 만족하는지 체크하는 루프를 도는 방식으로 문제를 풀었다.

n=10**8
p = [True for i in range(n)]
pl = []
 
cnt=0
for i in range(2,n):
    if p[i]:
        pl.append(i)
        for j in range(i,n,i): p[j]=False
        cnt+=1
    if cnt==10000:
        print(i)
        cnt=0
 
for x in reversed(pl):
    pp = str(x)
    if set(pp) == set([str(i) for i in range(1,len(pp)+1)]):
        print(f'solution:{pp}')
        break