JavaScript: Find all prime numbers below a given number

JavaScript Math: Exercise-69 with Solution

Find All Primes Below N

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.

For more Practice: Solve these Related Problems:

• Write a JavaScript function that generates all prime numbers below a given number using the Sieve of Eratosthenes algorithm.
• Write a JavaScript function that uses trial division to list all prime numbers up to a specified limit.
• Write a JavaScript function that returns an array of primes below N and optimizes the checking process for larger numbers.
• Write a JavaScript function that recursively generates prime numbers up to a given number and returns the result.

Improve this sample solution and post your code through Disqus.

Previous: Sum of the digits of a number.
Next: Reverse Polish notation in mathematical expression.