Sieve of Eratosthenes算法的代码

In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a simple, ancient algorithm for finding all prime numbers up to a specified integer.[1] It works efficiently for the smaller primes (below 10 million).[2] It was created by Eratosthenes, an ancient Greek mathematician. However, none of his mathematical works survived—the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. [素数的定义是,一个仅能被1和本身整除的自然数]

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

[可以通过以下的埃拉托色尼筛选法寻求所有小于整数n的素数]

Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).

[列出从2到n的一串连续自然数]

Initially, let p equal 2, the first prime number.

[开始,先把2当作第一个素数,并赋值给变量p]

Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)

[将该列自然数中划掉p的倍数]

Find the first number remaining on the list after p (this number is the next prime); replace p with this number.

[将剩下的自然数按原来顺序重新组成新的一列,并将第一个数赋给变量p]

Repeat steps 3 and 4 until p2 is greater than n.

[重复第三第四步,直到p的平方大于n]

All the remaining numbers in the list are prime.

[剩下的自然数就是所有小于n的素数]

import math

limit=1000000000

L=[True]*limit

def seive(x):

    for i in xrange(x*2,limit,x):

        L[i]=False map(seive,[2])

map(seive,xrange(3,int(math.ceil(math.sqrt(limit))),2))

primer=[]

for i in xrange(2,limit):

    if L[i]: primer.append(i)

print primer