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:
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.
for i in xrange(x*2,limit,x):
for i in xrange(2,limit):
if L[i]: primer.append(i)