[PE] Project Euler 7

프로젝트 오일러 7번 문제는 10001번째 소수를 찾으라는 문제다.

 

에라토스테네스의 체를 활용하여 나이브하게 접근하는 것을 시도해보도록 하자. 먼저, 1부터 10000사이에 있는 소수의 개수를 찾는 것부터 시작해본다.

n = 10001

l = [False for _ in range(n)]
p = []
for i in range(2, n):
    if not l[i]:
        p.append(i)
        for j in range(i, n, i):
            l[j] = True

print(len(p)) #1229

해당 코드에서는,

• 크기 10001짜리(즉, 마지막 인덱스가 10000) 리스트 l에 대해서
• 전부 False를 할당해두고
• i = 2일때부터 시작해서
• 만일 l[i]가 False이면 리스트 p에 더하고 (즉, p는 소수들이 들어있는 리스트)
• i의 배수 j에 대해 l[j]를 전부 True로 바꾸고(즉, j는 i의 배수이므로 소수가 아니다.)
• l[i]가 True이면 아무 작업도 하지 않고 넘어간다.
• 이 작업을 i에 1씩 더하면서 i=10000까지 계속 진행.

해당 작업을 쭉 진행한다. 이러면 10000까지의 소수가 전부 구해지는 식.

 

n=10000+1일때 소수가 1229개 찾아졌다. 위의 코드가 있으면 n 수를 키워가면서 10001번째 소수를 찾을 때까지 작업을 반복하는 것이 가능하다.

 

예를 들어, 

 

• n=20000+1일때 소수 개수 2262개
• n=80000+1일때 소수 개수 7837개

이쯤 왔으면, 소수 개수가 10001개가 되었을 때 해당 소수를 출력하는 코드를 짜도 괜찮다.

n = 160001

l = [False for _ in range(n)]
sol = 0
for i in range(2, n):
    if not l[i]:
        sol+=1
        if sol == 10001: 
            print(i)
            break
        for j in range(i, n, i):
            l[j] = True

i=160000일때까지 루프를 돌면서, 10001번째 소수를 찾으면 출력하고 루프를 빠져나오도록 코드를 수정했다. 이렇게 하면 정답을 찾을 수 있다.

 

위의 에라토스테네스의 체를 활용한 소수 찾기 방식은 굉장히 나이브해보이지만, 에라토스테네스의 체 자체의 시간복잡도가 O(n log log n)임을 고려하면 다른 문제들을 풀 때 활용도가 꽤 높다는 것을 알 수 있다. 다른 문제를 풀때 잘 활용해보자.