|
In this article, we will be demonstrating a JavaScript program for the Sieve of Eratosthenes algorithm.
The Sieve of Eratosthenes algorithm is an efficient way of getting all the prime numbers that exist in the given range e.g.,
Input: n =10
Output: 2 3 5 7
Input: n = 20
Output: 2 3 5 7 11 13 17 19
Approach
The programmatic approach for the algorithm is as follows:
- First, create a boolean array of length n+1 named prime with all values true
- Assign false for index 0 and 1 as these numbers are non-prime.
- The first prime number is 2, so start iterating from index 2 and assign all multiples of 2 as false to represent them as non-prime.
- Similarly, check for remaining indexes If true make all it’s multiple as false and continue till the loop ends i.e. i <= n.
- After this iterate the array store the indexes for which the prime value is true and return the output array.
Example: In this example, we will print all prime numbers up to the number 20.
Javascript
function sieveOfEratosthenes(n) {
let prime = new Array(n + 1).fill(true);
for (let i = 2; i <= n; ++i) {
if (prime[i])
for (j = i * i; j < n + 1; j += i) {
prime[j] = false;
}
}
primeArray = prime.reduce((acc, e, i) => {
if (e == true && i >= 2) {
acc.push(i);
}
return acc;
}, []);
return primeArray;
}
const num = 40;
console.log("Prime numbers up to "+ num+": "+ sieveOfEratosthenes(num));
|
Output
Prime numbers up to 40: 2,3,5,7,11,13,17,19,23,29,31,37
|
