Sieve of Eratosthenes

The sieve of Eratosthenes is an efficient method for computing primes upto a certain number. We first look at the algorithm and then give a program in Java for the same.

Algorithm

If you want to calculate all the primes up to x, then first write down the numbers from 2 to x. Remove the first number from this list (say y) and add it to the list of primes. Find all the multiples of y (excluding y) less than or equal to x and remove them out from the list. Repeat the above process until there you are left with no numbers.

We illustrate this procedure by finding all primes less than 15. (To indicate removal of an item from the list, we simply strike it out and to indicate addition of a number to the primes list, we put a tick mark over it)

First, we write down all the numbers from 2 to 15.

Iteration 1: Select the first number, 2. The multiples of 2 less than or equal to 15 are 4, 6, 8, 10, 12 and 14. We strike them out to indicate that they are not primes and mark 2 as a prime by keeping a tick mark over it.

Iteration 2: Now, we select the next number, 3. We again strike out the multiples of 3 less than or equal to 15 which are – 6, 9, 12, 15. Note that 6 and 12 have already been crossed out. If you want, you can strike them out again. It wouldn’t make any difference to the final result but there is no need of doing so. However, when we implement the program in Java, you will see that we do strike out these numbers a second time ( by setting a flag to false which is already false) which is simpler than first checking if it is already struck out ( the flag already set to false ). We also put a tick mark over 3 to indicate that it is a prime number.

Iteration 3: The number 5 is selected. The multiples of 5 are 10 and 15 which are already struck out. 5 is marked as a prime.

Iteration 4: 7 is selected. Here too, its only multiple 14 is already struck out. 7 is marked as a prime number.

Iteration 5: 11 is selected. It has no multiples up to 15. 11 is marked as a prime number.

Iteration 6: 13 is selected. As was the case with 11, 13 too doesn’t have any multiples in the list we are considering. We just mark 13 as a prime.

There are no more numbers left. So, the process stops. We have obtained 2, 3, 5, 7, 11 and 13 as the primes up to 15.

Implementation in Java

Following is the Java program for Sieve of Eratosthenes.

import java.util.Scanner;

Public class SieveOfEratosthenes {

Public void primes(int n) {
boolean[] primes = new boolean[n + 1];
for (int i = 2; i < primes.length; i++) {
primes[i] = true;
}
int num = 2;
while (true) {
for (int i = 2;; i++) {
int multiple = num * i;
if (multiple > n) {
break;
} else {
primes[multiple] = false;
}
}
boolean nextNumFound = false;
for (int i = num + 1; i < n + 1; i++) {
if (primes[i]) {
num = i;
nextNumFound = true;
break;
}
}
if (!nextNumFound) {
break;
}
}
for (int i = 0; i < primes.length; i++) {
if (primes[i]) {
System.out.println(i);
}
}
}

Public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“Enter a number: “);
int n = scanner.nextInt();
SieveOfEratosthenes sieve = new SieveOfEratosthenes();
sieve.primes(n);
}

}

The method sieve() accepts a parameter n up to which primes are to be calculated. We create a boolean array names primes of size (n+1) and set all the values (except 0 and 1) to true i.e. initially, we consider all numbers from 0 to n as primes (indicated by the boolean value true) As the execution proceeds, some of these true false will be changed to false to indicate that they are not primes. primes[i] tells us whether the number i is a prime or not.

We have a variable num to hold the current number we are considering i.e. the number whose multiples we are finding out. num is initially set to 2.

The while loop has two parts. In the first part, we find all the multiples of num up to n and set primes[multiple] to false. The multiples are found by multiply the number num with 2, 3, 4… in the for loop. If the multiple obtained is less than n, then it is present in the list we are considering and so we set primes[multiple] to false. If not, then it means that, we have crossed the limit n and so, we break out of the loop.

In the second part, we find the number which we will be considering in the next iteration of the while loop i.e. we find a new value for num. To do so, we use a for loop with its loop counter ranging from num+1 to n (inclusive) and check if primes[i] is true. If so, i is the next value for num. At the end of the loop if no value is found for num (indicated with a value of false for the variable nextNumFound), then it means that we have finished checking all the numbers and so, we break out of the for loop.

Finally, we print the primes.

Here is a sample run of the program.

Enter a number: 13
2
3
5
7
11
13