[ Project Euler With Python ] 10. Summation of primes

원문 : Summation of primes

---

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 입니다.

2000000 미만의 소수의 합을 구하십시오.

계속해서 나오는 소수 문제네요. [ 3. Largest prime factor ] 에서는 가장 큰 소인수를, [ 7. 10001 st pime ] 에서는 n 번째 소수를, 이 번에는 일정 이하의 소수의 합을 구하는 겁니다.

Brute-Force

def sum_primes_until( max ) : primes = list() primes.append( 2 ) primes.append( 3 ) primes.append( 5 ) i = 7 # second prime number, and odd number. sum = 2 + 3 + 5 while( i < max ) : is_prime = True for p in primes : # for each prime number if 0 == ( i % p ) : # i is evenly divided by prime number is_prime = False # i is not prime number break if is_prime : primes.append( i ) sum += i i += 2 # select next odd number if 0 == ( i % 5 ) : # if next odd number is multiple of 5 i + 2 # select next odd number return sum print( sum_primes_until( 2000000 ) )

일단 답은 142913828922 입니다.

나름대로 최적화를 한다고 했지만 O( mn ) 의 시간 복잡도를 가집니다. m 과 n 의 크기가 크므로 비용이 장난이 아닙니다. 한 10 분은 걸린 것 같군요.

소수와 관련해서 점점 더 극악한 조건을 제시하면서 결국에는 최적화를 더 하게 만드는군요.

Others Optimization

[ 7. 10001 st pime ] 의 공식 [ PDF ] 에서 최적화를 위해 사용한 전제들은 다음과 같습니다.

• 1 은 소수가 아님.
• 2 를 제외한 모든 소수는 홀수임.
• 3 보다 큰 모든 소수는 6k+/-1 로 작성될 수 있음.
• 어떤 수 n 은 루트 n 보다 큰 소수를 하나만 가지고 있을 수 있음.
• 어떤 수 n 에 대한 소수 테스트를 하기 위한 수열은 : n 을 나누는 루트 n 보다 작거나 같은 숫자 f 를 발견하지 못한다면, n 은 소수임 : n 의 유일한 소인수는 n 자체임.

뭔가 최적화의 여지가 상당히 많군요.

import math def isprime( n ) : if 1 == n : # 1 is not prime. return False elif n < 4 : return True # 2, 3 elif 0 == ( n % 2 ) : return False # even is not prime. elif n < 9 : return True # even is excluded, reamins 5, 7, 9. elif 0 == ( n % 3 ) : return False # multiple of 3 is excluded else : r = math.floor( math.sqrt( n ) ) f = 5 while f <= r : # check if n is divided by other prime( form of 6k+/-1 ) if 0 == ( n % f ) : return False if 0 == ( n % ( f + 2 ) ) : return False f += 6 return True sum = 2 for n in range( 3, 2000001, 2 ) : if isprime( n ) : sum += n print( sum )

실행해 보니 정상적인 결과가 나왔고, 무진장 빠르군요. 이것도 사실 O( mn ) 의 비용이 듭니다만, Brute-Force 방식보다는 m 과 n 의 크기가  작으므로 매우 빠릅니다. 거의 20 초 정도면 끝나는군요.