파이썬으로 소수 만들기

소수를 만드는 가장 좋은 방법은 "에라스토테네스의 체"입니다. 한글 위키피디아 페이지에서 오른쪽 상단의 움직이는 이미지를 보면 충분히 이해할 수 있을 겁니다.

이런 내용을 파이썬 코드로 구현하면 이렇게 됩니다. n 이하의 모든 소수를 리스트로 만들어 주는 거죠.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

로버트 윌리엄 행스(rwh)라는 사람이 stackoverflow에 올린 걸 가져온 겁니다. n이하 홀수들 중에서 체(seive)로 걸러지지 않는 것을 매우 효율적으로 찾아줍니다. 위의 url에 들어가 보면, 소수를 찾는 다른 방법들도 나와 있습니다. 각 알고리즘을 비교하는 표도 찾을 수 있고요. 저는 이 함수가 길이도 짧고, 의미하는 바도 간결하고, 실행 속도도 매우 빨라서 요즘에는 이것만 씁니다.

=====

이전에는 http://www.python-course.eu/list_comprehension.php 요기 페이지 마지막 예제로 나온 함수를 사용했었습니다. 위의 rwh_primes1보다 속도도 느리고, 무엇보다 버그가 있습니다. primes(50)을 찾아보면 49를 소수라고 판단하죠. 버그 고치라고 사이트 관리자에게 메일을 보낸 지 한참 되었는데 안 고치네요.