에라스토테네스의 체

특정한 수 미만의 소수들을 모두 찾는 방법중에 한개이다.

n이하의 모든 수 중에서, 이하 정수들의 배수를 모두 지워 마지막에 남는 수들은 1 ~ n 사이의 소수들만 남게 된다. (1은 기초수, 2는 예외)

마치 많은 수들 사이에서 배수들을 지워나가는 것이 체에 거르는 느낌이 든다.

예를들어 100이하의 소수들을 찾을 때, 이하 수(1~10)들의 배수들만 1~ 100 사이의 수에서 지우면 소수가 나온다.

소수들 간의 연관성이 아직 발견되지 않았기 때문에, 에라스토테네스의 체를 이용해서 미리 소수들의 리스트를 만들어 놓고 하는 것이 빠르다.

http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188

위의 주소에 들어가면 소수를 구하는 여러가지 방법들이 나와있는데, 

아래의 에라스토테네스의 체 코드를 이용해서 만드는 것이 가장 빠르다고 한다.

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]]