*901*

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

Input:N = 25Output: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);
}
}
```

Code language: Java (java)

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