Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
return array of primes below limit using Sieve of Atkin Algorithm http://en.wikipedia.org/wiki/Sieve_of_Atkin #JavaScript #primes
function sieveOfAtkin(limit){
var limitSqrt = Math.sqrt(limit);
var sieve = [];
var n;
//prime start from 2, and 3
sieve[2] = true;
sieve[3] = true;
for (var x = 1; x <= limitSqrt; x++) {
var xx = x*x;
for (var y = 1; y <= limitSqrt; y++) {
var yy = y*y;
if (xx + yy >= limit) {
break;
}
// first quadratic using m = 12 and r in R1 = {r : 1, 5}
n = (4 * xx) + (yy);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
sieve[n] = !sieve[n];
}
// second quadratic using m = 12 and r in R2 = {r : 7}
n = (3 * xx) + (yy);
if (n <= limit && (n % 12 == 7)) {
sieve[n] = !sieve[n];
}
// third quadratic using m = 12 and r in R3 = {r : 11}
n = (3 * xx) - (yy);
if (x > y && n <= limit && (n % 12 == 11)) {
sieve[n] = !sieve[n];
}
}
}
// false each primes multiples
for (n = 5; n <= limitSqrt; n++) {
if (sieve[n]) {
x = n * n;
for (i = x; i <= limit; i += x) {
sieve[i] = false;
}
}
}
//primes values are the one which sieve[x] = true
return sieve;
}
primes = sieveOfAtkin(5000);
@kramtark

This comment has been minimized.

Copy link

commented Jun 23, 2014

Is line 39 missing a var declaration for i? I don't see it defined as such elsewhere. Is this permitted in Javascript?

@rizalp

This comment has been minimized.

Copy link
Owner Author

commented Sep 25, 2014

@kramtark Yes it is permitted. Js is function-scoped, not block scoped like C or Java. So whether we define var or not in the for loop declaration, it doesn't matter because that variable only exist in sieveOfAtkin function...

The only danger, is if you have variable i outside of sieveOfAtkin. It will be overridden.

@axelduch

This comment has been minimized.

Copy link

commented Feb 22, 2015

@rizalp This is not true, and strict mode would throw an error because you are defining window.i as it is never "declared" with the var keyword.

Therefore i pollutes the global scope.

Anyways, thank you for sharing this implementation :)

@scolladon

This comment has been minimized.

Copy link

commented Aug 13, 2015

Why line line 12 y is instanciate with 1 ? Should it not be y = x ?

@farskid

This comment has been minimized.

Copy link

commented Jul 15, 2016

This a performance friendly implementation as stated in wikipedia. But the output seems to be useless cause indexes of an array as the prime numbers cant be used anywhere.
See this link for a converter I coded to return a list of actual prime numbers.
https://gist.github.com/farskid/3501b1b981607483a46b76d61e092e6e

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.