Find the first N prime numbers. (Method 4) [Sieve of Eratosthenes]

1.7K

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.

• Method 1
• Method 2
• Method 3

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);
  }
}
Code language: Java (java)

A working example of the code can be found here.
Time Complexity: O(N log (log N))