Question:Given an integer N, find the prime numbers in that range from 1 to N.

Input:N = 25

Output:2, 3, 5, 7, 11, 13, 17, 19, 23

We have several ways of finding prime numbers. Some of the methods are discussed in the these posts.

In this post we will find the first N prime numbers using the ** Sieve of Eratosthenes**. This technique is helpful in scenarios when we have to give immediate results and we need to query the prime numbers again and again. This is a pre-processing technique where we store all the prime numbers to a limit N, and then keep on querying as per our needs. Let us understand how does a Sieve of Eratosthenes work.

Suppose we want to find prime numbers till **N = 30**. Declare a linear boolean array of size 30. The array below looks like a 2d array but it is just a linear array from 1-30.

[1] True | [2] True | [3] True | [4] True | [5] True | [6] True | [7] True | [8] True | [9] True | [10] True |

[11] True | [12] True | [13] True | [14] True | [15] True | [16] True | [17] True | [18] True | [19] True | [20] True |

[21] True | [22] True | [23] True | [24] True | [25] True | [26] True | [27] True | [28] True | [29] True | [30] True |

Ignore the first element and start with [2]. Except that element mark all its multiples as False. In this case leave ‘2’ and mark all the multiples of ‘2’ in the array as false. So we get

[1] True | [2] True | [3] True | [4] False | [5] True | [6] False | [7] True | [8] False | [9] True | [10] False |

[11] True | [12] False | [13] True | [14] False | [15] True | [16] False | [17] True | [18] False | [19] True | [20] False |

[21] True | [22] False | [23] True | [24] False | [25] True | [26] False | [27] True | [28] False | [29] True | [30] False |

Move to element [3]. Leaving ‘3’ mark all its multiples as False. If the element is already false, just ignore it. We now get

[1] True | [2] True | [3] True | [4] False | [5] True | [6] False | [7] True | [8] False | [9] False | [10] False |

[11] True | [12] False | [13] True | [14] False | [15] False | [16] False | [17] True | [18] False | [19] True | [20] False |

[21] False | [22] False | [23] True | [24] False | [25] True | [26] False | [27] False | [28] False | [29] True | [30] False |

Since 4 is already False, move to the next element 5. Ignore 5 and mark all its multiples as False.

[1] True | [2] True | [3] True | [4] False | [5] True | [6] False | [7] True | [8] False | [9] False | [10] False |

[11] True | [12] False | [13] True | [14] False | [15] False | [16] False | [17] True | [18] False | [19] True | [20] False |

[21] False | [22] False | [23] True | [24] False | [25] False | [26] False | [27] False | [28] False | [29] True | [30] False |

Continue this process for a larger array till we reach the last element. In this case the above array is our final array.

The given code implements the above algorithm

// code obtained from studyalgorithms.com public class SieveOfEratosthenes { static void sieveOfEratosthenes(int n) { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in isPrime[i] will // finally be false if i is Not a prime, else true. boolean isPrime[] = new boolean[n + 1]; for (int i = 0; i < n; i++) isPrime[i] = true; for (int number = 2; number * number <= n; number++) { // If prime[p] is true, then it is a prime number // we need to ignore it and now mark all it's multiples if (isPrime[number] == true) { // Update all multiples of p for (int i = number * 2; i <= n; i += number) isPrime[i] = false; } } // Print all prime numbers // At this point only the numbers which are set as true are prime. for (int i = 2; i <= n; i++) { if (isPrime[i] == true) System.out.print(i + " "); } } public static void main(String[] args) { sieveOfEratosthenes(30); } }

A working example of the code can be found here.

* Time Complexity: *O(N log (log N))