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