Problem_010_Summation of primes

[그림 01] Problem 010 문제

문제 설명

문제 이름 : 소수의 합

문제 내용 : 10 이하의 소수들의 합을 보면 2 + 3 + 5 + 7로 17이 나옵니다. 그렇다면 2,000,000 미만의 소수들의 합은 무엇입니까?

우리는 조건이 매우 간단하다는 것을 알 수 있습니다. 저도 그렇게 생각했습니다.

그러나... 저는 이 간단함에 여유를 부리고 시간을 매우 소비할 뻔 했습니다.

1. 소수 리스트를 구해야 함

2. 구해진 소수 리스트를 통해 모든 합을 구함

이제 소스를 작성해보도록 합시다.

소수를 구하는 방법이 이 문제의 핵심이라고 생각됩니다.

먼저 제가 가장 빠르다고 생각했던 소수 구하는 방법으로 작성해보았습니다.

소스코드

- vol01

#Problem 010
#Python 3 version source

#Get the sum of all the primes below 2,000,000

def getPrime(Number):
	primeList = [2]
	num = 3
	count = 100000
	
	while(num < Number):
		for x in primeList:
			if num % x == 0:
				break
			elif x == primeList[-1]:
				primeList.append(num)
				break
		if num == count:
			print(primeList)
			count += 100000
		
		num += 1
		
	return primeList
	
if __name__ == "__main__":
	Main_primeList = getPrime(2000000)
	sum = 0
	
	for i in Main_primeList:
		sum += i
	
	print(sum)

간단하게 getPrime으로 작성해보았습니다. 지금까지 제가 애용하던 소수 구하기입니다.

처음 primeList 는 2로 시작하고 시작 숫자는 3으로 시작합니다.

primeList에 추가되는 소수 리스트들로 나누어떨어지는 숫자라면 이 숫자는 소수가 아닌 것으로 판단할 수 있습니다.

이 알고리즘은 일종의 에라스토테네스의 체와 비슷하다고 할 수 있습니다. 

그러나 이것은 진정한 에라스토테네스의 체가 아니었습니다.

2의 배수, 3의 배수, 5의 배수... 소수의 배수로 이루어진 값들을 체로 모두 만들어낸 후 이를 모두 없애고, 나머지가 소수라는 것이 진정한 에라스토테네스의 값인 것입니다.

그렇다면 우리는 알고리즘을 수정할 필요가 있습니다.(매우매우!!)

count는 그냥 100,000씩 끊어서 체크해보기 위함입니다. 하하..

시간은 1시간 정도 걸리려나요..? 1분동안 돌려보았지만 400,000까지는 해보았습니다. 그 이상은 하지 못했지요.(너무 오래걸려서..)

저는 여기서 getPrime함수의 한계를 느꼈습니다. 

이제 진정한 에라스토테네스의 함수로 넘어가볼까요???

먼저 다음 소스를 확인해주시기 바랍니다.

#Sieve Test
import time

def sieve(Limit):
	prime = set()
	not_prime = set()

	for i in range(2, Limit+1):
		if i not in not_prime:
			prime.add(i)
			for j in range(i*i, Limit+1, i):
				not_prime.add(j)
				
	return prime

start_time = time.time()	
primeList = sieve(2000000)
print(len(primeList))
end_time = time.time()

print("Time : ", end_time - start_time)

위의 소스는 에라스토테네스의 체를 시험한 것입니다.

참고 URL : http://ledgku.tistory.com/61

위의 URL은 에라스토테네스의 정리를 프로그램적으로 잘 설명해주셨습니다.

먼저 primeList와 not_primeList에 대한 초기값을 지정해줍니다.

list보다는 set을 지향합니다.

  ※ list는 중복이 되지만, set은 자동적으로 중복을 걸러내줍니다.

먼저 i의 제곱(소수의 제곱은 소수가 아니므로)부터 i만큼씩 배수를 체크합니다.

(2의 배수이면, 4부터 6, 8, 10 ...... n까지)

(3의 배수이면, 9부터 12, 15, 18 ... n까지)

만약 배수가 아닌 값은 primeList에 추가합니다.

이렇게 하면 not_primeList와 primeList가 구분되고, 우리는 온전한 primeList만 뽑아낼 수 있게 됩니다.

시간은 엄청 짧습니다!!

제 태블릿, limit == 2,000,000을 기준으로 1.27초 가량 걸렸습니다.

그렇다면 저 함수를 이용하여 온전한 primeList를 가져오면 좋을 것 같습니다.

- vol 02

두번째 버전의 소스입니다.

#Problem 010
#Python 3 version source

def sieve(Limit):
	prime = set()
	not_prime = set()

	for i in range(2, Limit+1):
		if i not in not_prime:
			prime.add(i)
			for j in range(i*i, Limit+1, i):
				not_prime.add(j)
				
	return prime
	
if __name__ == "__main__":
	Main_primeList = sieve(2000000)
	sum = 0
	
	for i in Main_primeList:
		sum += i
	
	print(sum)

이 함수를 이용하면 2초 가량 걸립니다용. 이번에는 나름 뿌듯합니다.

물론 sieve라는 건 살짝 답안지를 볼까 하는 욕구에서 비롯된 것이지만, 힌트를 얻고 답안지를 안 봤으니 나름 스스로 토닥토닥해줄 수 있지용.

이제 제가 답안지라고 생각하는 소스를 참고해봅시다.

참고 URL : http://www.s-anand.net/euler.html

sieve = [True] * 2000000    # Sieve is faster for 2M primes

def mark(sieve, x):
    for i in range(x+x, len(sieve), x):
        sieve[i] = False

for x in range(2, int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve, x)
print(sum(i for i in range(2, len(sieve)) if sieve[i]))

sieve 전역 변수는 True로 2,000,000개를 초기화해놓은 배열입니다.

mark함수는 초기화된 sieve와 배수로 지정할 소수를 넘겨줍니다.

그리고 모두 종료되면 모든 합을 구합니다.

일단 대단하다고 느껴집니당. 대단하지만, 이제는 조금 경쟁심이 생기네요 *^^*