The sieve of Eratosthenes is an efficient method for computing primes up to 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 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 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 show the removal of an item from the list, we strike it out and to indicate the addition of a number to the primes list, we put a tick mark over it)

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

sieve of eratosthenes - numbers 2 to 15Iteration 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 struck them out to show that they are not primes and mark 2 as a prime by keeping a tick mark over it.

sieve of eratosthenes - selecting 2Iteration 2: Now, we select the next number, 3. Again, we strike out 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. You can strike them out again. It wouldn’t make any difference to the result, but there is no need to do so. However, when we implement the program in Java, you will see that we 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.

sieve of eratosthenes - selecting 3Iteration 3: Number 5 is selected. The multiples of 5 are 10 and 15 which are all ready struck out. 5 is marked as a prime.

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

Iteration 5: 11 has been selected. There are no multiples of up to 15. 11 is marked as a prime number.

Iteration 6: 13 is selected. As with 11, 13 doesn’t have any multiples on the list we are considering. We need to mark 13 as prime.

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

Implementation in Java

The following is the Java program for the 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 a 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 them for a loop.

Finally, we print the primes.

Here is a sample run of the program.

Enter number: 13
2
3
5
7
11
13