Sieves – Find all prime numbers below a given number

sieve-of-eratosthenes.js

// See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

function sieveOfEratosthenes(n) {
  // Create a boolean array "prime[0..n]" and
  // initialize all entries it as true.
  // A value in prime[i] will finally be false
  // if i is Not a prime, else true.
  let prime = new Array(n + 1).fill(true);

  // Create the Sieve
  for (let p = 2; p * p <= n; p++) {
    // If prime[p] is not changed, then it is
    // a prime
    if (prime[p] === true) {
      // Update all multiples of p
      for (let i = p * p; i <= n; i += p)
        prime[i] = false;
    }
  }

  // Print all prime numbers
  let primes = [];
  for (let p = 2; p <= n; p++)
    if (prime[p])
      primes.push(p);

  return primes;
}

// Find the primes less than 100
let primes = sieveOfEratosthenes(100);
// console.log(primes); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

sieve-of-sundaram.js

// See https://en.wikipedia.org/wiki/Sieve_of_Sundaram

function sieveOfSundaram(n) {
  // Create a boolean array "prime[0..n]" and
  // initialize all entries it as true.
  // A value in prime[i] will finally be false
  // if i is Not a prime, else true.
  let prime = new Array(n + 1).fill(true);

  // Initialize the p integers to be used
  // in the Sieve
  let p = 2 * n + 2;

  // Create the Sieve
  for (let i = 1; i <= n; i++)
    for (let j = i; j <= (n - i) / (2 * i + 1); j++)
      prime[i + j + 2 * i * j] = false;

  // Print the primes that are
  // not marked in the Sieve
  let primes = [];
  for (let i = 1; i <= n; i++)
    if (prime[i])
      primes.push(p - 2 * i);

  return primes;
}

// Find the primes less than 100
let primes = sieveOfSundaram(100);
// console.log(primes); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]