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. It works efficiently for the smaller primes (below 10 million). 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,)

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