The next number not yet crossed out in the list after 3 is 5 cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. The next number in the list after 2 is 3 cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list): The first number in the list is 2 cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list): To find all the prime numbers less than or equal to 30, proceed as follows.įirst, generate a list of integers from 2 to 30:Ģ 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds (i.e., numbers coprime with 2), and counting in the correspondingly adjusted increments so that only such multiples of p are generated that are coprime with those small primes, in the first place. This actually appears in the original algorithm. , n), and count in increments of 2 p from p 2 in step 3, thus marking only odd multiples of p. Īnother refinement is to initially list odd numbers only, (3, 5. This means that the algorithm is allowed to terminate in step 4 when p 2 is greater than n. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5).Īs a refinement, it is sufficient to mark the numbers in step 3 starting from p 2, as all the smaller multiples of p will have already been marked at that point. The main idea here is that every value given to p will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3. Find the smallest number in the list greater than p that is not marked.Enumerate the multiples of p by counting in increments of p from 2 p to n, and mark them in the list (these will be 2 p, 3 p, 4 p.Initially, let p equal 2, the smallest prime number.
Create a list of consecutive integers from 2 through n: (2, 3, 4.To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method: Ī prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself. It may be used to find primes in arithmetic progressions. One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. CE book, which describes it and attributes it to Eratosthenes of Cyrene, a 3rd cent. The earliest known reference to the sieve ( Ancient Greek: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic, an early 2nd cent. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.
This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).