##
Sieve of Eratosthenes

Posted by Chantique under

Design and Analysis of Algorithms
1 Comment
**ALGORITHM ***Sieve_of_Eratosthenes*(*n*)

// Generates consecutive primes not exceeding *n* by sieve of Eratosthenes

// Input : A positive integer *n *>= 2

// Output : Array *L* of all prime numbers less than or equal to *n*

**for ***p* <- 2 **to ***n* **do** *A*[*p*] <- *p*

**for ***p* <- 2 **to **floor(sqrt(*n*)) **do**

**if ***A*[*p*] != 0 // *p* hasn’t been eliminated on previous passes

*j* <- *p* * *p*

**while ***j *<= *n ***do**

* A*[*j*] <- 0 // mark an element as eliminated

* j *<- *j *+ *p*

// copy the remaining elements of *A* to array *L *of the primes

*i* <- 0

**for ***p *<- 2 **to ***n ***do**

**if ***A*[*p*] != 0

*L*[*i*] <- *A*[*p*]

*i *<- *i *+ 1

**return ***L*

The algorithm starts by initializing a list of prime candidates with consecutive integers from 2 to *n*. Then, on the first iteration of the algorithm, it eliminates from the list all multiples of 2, i.e., 4, 6, and so on. Then it moves to the next item on the list, which is 3, and eliminates its multiples. (In this straight forward version, there is an overhead because some numbers, such as 6, are eliminated more than once.) No pass for number 4 is needed : since 4 itself and all its multiples are also multiples of 2, they were already eliminated on a previous pass. (By similar reasoning, we need not consider multiples of any eliminated number.) The next remaining number on the list, which is used on the third pass, is 5. The algorithm continues in this fashion until no more numbers can be eliminated from the list. The remaining integers of the list are the primes needed.

### Like this:

Like Loading...

Thursday, 6 February 2014 at 0:57:17

This is certainly special cool. I’ve been looking through the bunch on-line and also really

liked this unique adaptation.