Hello,

This blog is to help you to understand Sieve of Eratosthenes algorithm for prime number generation in easiest way. This algorithm is to calculate the prime number up to a limit with lesser time complexity, but it takes O(n) extra space  for the computation of prime numbers.

The algorithm takes all the numbers from 2 to N all initially unmarked. It starts from 2 and marks all the multiple of 2 except 2 until multiple is less then or equal to limit value. After that next number which is not marked will be selected and all the multiples of him should be marked for the given range for which multiple value is lesser then the given limit. This process is repeated until the selected number is greater then √N.

Lets take an example

Suppose we have our limit as 20, now we have to get all prime numbers up to 20.

We should take an array of size n+1 with initial value as 0 at every cell, as each array block index will represent the number and flag value(marked of unmarked) will be stored as value at that index of array.

int[] arr = new int[n+1]

and n = 20

The square root of 20 is 4.47 and its integer value of 4.47 is 4. So we will iterate only form 2 to 4. 

Our initial array is.

[  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]

We take 2 as the staring point and mark all the multiples of 2 up to the limit.

[  0,  0,  0,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1]

Now next index value to be chosen should be marked as 0,on going one step further we found that at index 3  value is 0 so 3 is picked. And its multiples are marked.

[  0,  0,  0,  0,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1]

4 is marked so we can't pick it. We will not go for further values as we said that we will only iterate up to square root of the limit value.

After that we left with an array whose some element are marked 1 and some 0.

arr   = [  0,  0,  0,  0,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,  1]

index =   0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  20

Now this array will be traversed from 2 to limit value. if value at that index is unmarked (0) then that number would be prime else would be composite.

2, 3, 5, 7, 11, 13, 17 and 19 are the indexes on which values were 0 or unmarked. So these are our prime numbers up to 20. 

This is a pictorial representation Sieve of Eratosthenes for limit value 100

Java Program implementing Sieve of Eratosthenes algorithm

import java.util.Scanner;

public class SOE {
	public static void main(String[] args) {
		System.out.print("Enter Your Limit Value : ");
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		int[] arr = new int[n+1];
		int sqrt = (int)Math.sqrt(n);
		//System.out.println(sqrt);
		for ( int i = 2; i <= sqrt; i++) {
			if (arr[i] == 0) {
				//System.out.println(" " + i);
				for ( int j = 2; j <= n; j++) {
					if (j*i > n)
						break;
					arr[i*j] = 1;
				}
			}
		}
		System.out.println("Prime number up to " + n + " are ");
		for ( int i = 2 ; i < n; i++) {
			if (arr[i] == 0)
				System.out.print(i + " ");
		}
			
		System.out.println();
	}
}

And the output taking limit value as 100 will be

Enter Your Limit Value : 100
Prime number up to 100 are 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

Thanks for reading  :)