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.

## Sieve of Eratosthenes Java 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 it leaves you 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 show the addition of a number to the primes list; we put a tick mark over it).

### Prime numbers

First, we write 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 struck them out to show that they are not prime and mark 2 as a prime by keeping a tick mark over it. Iteration 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 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 show that it is a prime number. Iteration 3: We select Number 5. There are multiples of 5 that are 10 and 15, which have already struck out. 5 is marked as prime. Iteration 4: 7 is selected. Here too, only multiple 14 are already struck out. 7 is marked as a prime number. Iteration 5: We have selected 11. 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 that 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 of Java Code

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 of 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 (showed 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 was 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 can be found by multiplying the number num with 2, 3, 4… in the for a loop. If the multiple got 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 consider 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 we find no value 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