{{ message }}

Instantly share code, notes, and snippets.

# rizalp/JavaScript Sieve Of Atkin.js

Created May 3, 2013
return array of primes below limit using Sieve of Atkin Algorithm http://en.wikipedia.org/wiki/Sieve_of_Atkin #JavaScript #primes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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);

### scolladon commented Aug 13, 2015

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

### farskid 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