Skip to content

Instantly share code, notes, and snippets.

@danielpradilla
Created March 8, 2017 15:42
Show Gist options
  • Save danielpradilla/6309b894e19dce1e0e528ee9e762ef97 to your computer and use it in GitHub Desktop.
Save danielpradilla/6309b894e19dce1e0e528ee9e762ef97 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
/*jshint esnext: true */
/*
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the smallest prime number.
3. Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
*/
function* numberMaker(max) {
var index = 1;
while(index<=max)
yield index++;
}
function sieve(max){
let numbers = [... numberMaker(max)];
let marked = [];
let primes = [];
let p=2;
while (p<max) {
for (n=p; n<=max; n=n+p) {
if (marked.indexOf(n)<0 && n!==p){
//mark the number if it's not marked and not p
marked.push(n);
}
}
//make p the next highest unmarked number
p = numbers.find(number=> (number > p && marked.indexOf(number)<0));
}
//get all the numbers which are not marked
primes = numbers.filter(number => marked.indexOf(number)<0)
return primes;
}
console.log(sieve(2000));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment