Skip to content

Instantly share code, notes, and snippets.

@theanam
Last active September 29, 2015 09:39
Show Gist options
  • Save theanam/1a2ebaa5328973a8e12f to your computer and use it in GitHub Desktop.
Save theanam/1a2ebaa5328973a8e12f to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in JavaScript
/*
Sample Implementation of Sieve algorithm for 1-3000
not optimized yet
*/
var ar = [];
var max = 3000;
//loop should run only till the square root of the maximum
var maxloop = Math.round(Math.sqrt(max));
for(a=0;a<max;a++){
ar.push(true);
}
function isPrime(n){
if(!n || n==1)
return false;
var end = Math.floor(Math.sqrt(n));
//console.log(end);
for(i=2;i<end;i++){
if(n%i==0)
return false;
}
//console.log(n)
return true;
}
for(j=0;j<=maxloop;j++){
if(ar[j]){
if(isPrime(j)){
for(x=(j+j);x<max;x+=j){
ar[x]=false;
}
}
else{
ar[j]=false;
}
}
}
ar.filter(function(n,i){
n && console.log(i)
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment