[Python example] 소수 구하기 #2 (에라토스테네스의 체)

이번에는 소수를 구하는 또다른 방법을 구현해 보겠습니다.

소수는 예전에 구한 방법 이외에도, '에라토스테네스의 체'라는 방법을 이용해서 구할 수도 있습니다.


그림출처: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

이 알고리즘을 설명하자면,

1. 2에서부터 n까지의 수를 체에 넣고,
2. 체에서 가장 작은 값을 소수로 체크하고, 그 수의 배수들을 모두 제외시킵니다.
3. 위 2번 과정을 반복합니다.

여러가지 방법을 사용할 수 있겠지만, 딕셔너리를 이용해서 구현하면 다음과 같습니다.

# -*- coding: utf-8 -*-
import sys

if __name__=="__main__":
    print( sys.version )
    N = int( input("input a number : ") )
    #init
    sieve = {}
    for i in range(2, N+1):
        sieve[i] = 0
       
    # Sieve of Eratosthenes
    for i in range(2, N+1):
        if sieve[i]==0:
            n=2
            while i*n <= N:
                sieve[i*n]=1
                n+=1

    #print results
    for i in range(2, N+1):
        if sieve[i]==0:
            print( i, end="," )
    print()       
    input("press any key")

100을 넣고 실행해 보면 결과는 다음과 같습니다.

3.0 (r30:67507, Dec  3 2008, 20:14:27) [MSC v.1500 32 bit (Intel)]
input a number : 100
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
press any key