Project Euler. #10. Summation of primes

By | 2013/02/26

Project Euler (http://projecteuler.net/) 문제10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

10 이하의 소수들의 합은 2 + 3 + 5 + 7 = 17 이다.

2백만 이하의 모든 소수들의 합을 구하여라.


primes= []

def isPrime(n):
    for p in primes:
        if n%p==0:
            return False
    return True

sum=0
for i in range(2,2000000):
    if isPrime(i):
        primes.append(i)
        sum+=i
print sum

특정 수 n이 소수인지를 판별하기 위해 2에서 n-1까지의 모든 수로 나눠보는 것은 매우 비효율적이므로, n 미만의 소수들로만 나눠보기로 했다. 어짜피 n 미만의 숫자 중 n을 나누어 떨어지게 할 수 있는 '소수가 아닌 수'도 있긴 하지만 이런 수들은 결국 소인수 분해를 하면 소스들로 구성되어 있기 때문에, n 미만의 소수들로만 나눠봤을 때 한번도 나누어 떨어지지 않으면 n 또한 소수임이 분명하다.

그래서 2부터 2000000까지 계속해서 소수임을 판별하기 위하여 소수가 발견될 때 마다 primes 라는 리스트에 이 소수를 추가하였고, 이 리스트의 요소들로 특정 수 n을 나누어보면서 n이 소수인지 아닌지를 판단하였다.

이렇게 계산하면 금방 결과가 나올 줄 알았는데 2000000이라는 숫자가 워낙에 크다보니 답이 나오는데 1000여초가 조금 넘게 걸렸다. 이렇게 풀라고 만든 문제가 아닐텐데...


primes= []

def isPrime(n):
    for p in range(2,int(n**(0.5))):
        if n%p==0:
            return False
    return True

sum=0
for i in range(2,2000000):
    if isPrime(i):
        primes.append(i)
        sum+=i
print sum

그냥 예전에 Project Euler에서 소수 관련 문제가 나왔을 때 풀었던 것 처럼, n이 소수임을 판별하기 위하여 2에서 \sqrt{n}까지만 나눠보았다. (어짜피 n을 소인수 분해하면 \sqrt{n}보다 큰 소수는 존재하지 않기 때문이다.

이렇게 해결하니 30여초만에 문제가 해결되었다. 앞의 소스에 비해서는 비약적인 발전이긴 하지만, 30여초도 길다. 일단 정답을 입력 후, 다른 사람들이 해결한 방법을 찾아보았다. 조금 더 빠른 방법으로 이 문제를 해결하려는 다양한 시도들이 보였는데 그 중 돋보이는 해답이 눈에 들어왔다.


#Developed by derhesse on Project Euler

def getPrimeNumbers(n):
   list_of_primes = {}
   for i in range(2,n+1):
      list_of_primes[i] = True
   view_primes = list_of_primes.keys()
   for x in view_primes:
      if list_of_primes[x] == True:
         for z in range(x*x,n+1,x):
            list_of_primes[z] = False
   result_list = []
   for x in view_primes:
      if list_of_primes[x] == True:
         result_list.append(x) 
   return result_list

temp_list = getPrimeNumbers(2000000)
sum_of_primes = 0
for i in temp_list:
   sum_of_primes += i
print(sum_of_primes)

이렇게 하면 단 2~3초 만에 문제가 해결된다. 1999999개의 요소를 가진 사전형 변수 list_of_primes를 만들고, 각각의 키는 2에서 2000000, 값은 전부 True도 초기화하였다. 그리고 2부터 2000000까지의 숫자들을 순서대로 가져와서 해당 숫자의 제곱부터 n까지의 숫자중 해당 숫자의 배수들은 모두 소수가 아닌 것(False)으로 처리하고 나면, 소수(True)만 남게 된다. 이 True값들의 합만 계산하면 끝!

이렇게 답을 알고 나면 매우 단순한데, 이것을 생각해내기가 이렇게 어렵다니.
여기서 그냥 멈추기에는 들인 시간이 아까워서, 위의 코드를 조금 단순화 시켜보았다.


def getPrimeNumbers(n):
   list_of_primes = {}
   for i in range(2,n+1):
      list_of_primes[i] = True

   for x in list_of_primes.keys():
      if list_of_primes[x] == True:
         for z in range(x*x,n+1,x):
            list_of_primes[z] = False

   return [x for x in list_of_primes.keys() if list_of_primes[x] == True]

print sum(getPrimeNumbers(2000000))

Project Euler의 1번 문제부터 10번 문제까지 순서대로 다 풀고 나니 Decathlete 뱃지가 생겼다. 10개의 문제를 순서대로 풀어내면 이 뱃지가 생긴단다. 현재 이 뱃지를 가진 사람은 57285명. 생각보다 적다. 이제 순서대로 100개의 문제를 푼 사람한테 주어지는 뱃지가 갖고싶어 진다.

과연 어느 세월에 ...