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:


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


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


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


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


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


All the remaining numbers in the list are prime.


import math



def seive(x):

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

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



for i in xrange(2,limit):

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

print primer