JavaScript: Find all prime numbers below a given number

JavaScript Math: Exercise-69 with Solution

Write a JavaScript program to find all prime numbers below a given number.

From Wikipedia -
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

Sample Data:
(5) -> [2, 3, 5]
(11) -> [2, 3, 5, 7, 11]
(30) -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Sample Solution:

JavaScript Code:

``````/**
* Generates all prime numbers less than or equal to the given number using the Sieve of Eratosthenes algorithm.
* @param {number} n - The upper limit of the prime numbers to be generated.
* @returns {number[]} - An array containing all prime numbers less than or equal to 'n'.
*/
function sieve_Of_Eratosthenes(n) {
// Initialize an array to mark whether each number is prime or not
const sieve = [];
// Initialize an array to store the prime numbers
const primes_set = [];

// Iterate over each number from 2 to 'n'
for (let i = 2; i <= n; ++i) {
// If 'i' is not marked as non-prime, it is a prime number
if (!sieve[i]) {
// Add 'i' to the list of prime numbers
primes_set.push(i);
// Mark all multiples of 'i' as non-prime
for (let j = i << 1; j <= n; j += i) {
sieve[j] = true;
}
}
}

// Return the list of prime numbers
return primes_set;
}

// Test the function with different values of 'n'
console.log(sieve_Of_Eratosthenes(5));  // Output: [2, 3, 5]
console.log(sieve_Of_Eratosthenes(11)); // Output: [2, 3, 5, 7, 11]
console.log(sieve_Of_Eratosthenes(30)); // Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
```

Output:

```// [object Array] (3)
[2,3,5]
// [object Array] (5)
[2,3,5,7,11]
// [object Array] (10)
[2,3,5,7,11,13,17,19,23,29]
```

Flowchart:

Live Demo:

See the Pen javascript-math-exercise-69 by w3resource (@w3resource) on CodePen.

Improve this sample solution and post your code through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿