Solving Sieve Of Eratosthenes

the Sieve of Eratosthenes algorithm is known for fining all prime numbers up to a given number, so for example if we were give the number 20 we must return an array of all prime numbers found from 0 to 20

##Example

number: 18
output: [ 2, 3, 5, 7, 9, 11, 13, 15, 17 ]

Input : Number
Output : Array of all prime numbers.

Implementation #

function sieveOfEratosthenes(n) {
  var primes = [];

  for (var i = 0; i <= n; i++) {
    primes[i] = true;
  }

  // Base Cases since 0,1 is not prime numbers
  primes[0] = false;
  primes[1] = false;

  //Stop looping through at the square root of n becuase will be find them before we reach this point
  for (var i = 2; i <= Math.sqrt(n); i++) {
    // loop to the multuple for each number and mark it as non-prime
    for (var j = 2; i * j <= n; i++) {
      primes[i * j] = false;
    }
  }

  var result = [];
  for (var i = 0; i <= primes.length; i++) {
    if (primes[i]) result.push(i);
  }

  return result;
}

The code is availalbe here : https://repl.it/@ahmd1/Sieve-Of-Eratosthenes

Credits #

Photo by Chris Brignola

← Home