Implement sieve of Eratosthenes using javascript. A simple, ancient algorithm for finding all prime numbers up to any given limit.

sieveOfEratosthenes.js

function sieve(x) {
	let counter = 0;
  let seq = Array(x - 1).fill(2).map((e, i) => e + i);
  let primes = [];
  while (true) {
    if(seq.length === 0){
    	console.log(`main loop count : ${counter}`);
      return primes;
    }
      
    primes.push(seq[0]);
    seq = seq.filter(e => {
    	counter++;
    	return e % primes[primes.length - 1] !== 0;
    });
  }
}

/*埃拉托斯特尼篩法，是一種簡單且年代久遠的篩法，用來找出一定範圍內所有的質數。*/
function sieveOfEratosthenes(x) {
	let counter = 0;
  let seq = Array(x+1).fill(true);
  let sqrt = Math.sqrt(x);
  for(let i=2;i<=sqrt;i++){
  	if(seq[i]){
    	for(let j = Math.pow(i,2);j<=x;j+=i){
      	seq[j] = false;
        counter++;
      }
    }
  }
  console.log(`main loop count : ${counter}`);
  return seq.reduce((acc,e,i)=>{
  	if(e && i>=2)
    	acc.push(i);
    return acc;
  },[])
}

let N=10000;
console.log("sieve\n",sieve(N));
console.log("sieveOfEratosthenes\n",sieveOfEratosthenes(N));

/*
main loop count : 777860
sieve
(1229) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...]
main loop count : 16981
sieveOfEratosthenes
(1229) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...]
*/