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

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

0 comment

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.

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

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

Since 4 is already False, move to the next element 5. Ignore 5 and mark all its multiples as 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

.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
.hljs > mark.shcb-loc { background-color: #ddf6ff; }// 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))

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More