Margaret Margaret - 1 month ago 4x
Javascript Question

Sieve of Eratosthenes in Javascript?

so I was trying to translate this pseudocode from Wikipedia into Javascript:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i^2, i^2+i, i^2+2i, i^2+3i, ..., not exceeding n :
A[j] := false

Output: all i such that A[i] is true.

And this is as far as I got:

function getPrimes(num) {
var a = [];
for (i=2;i<=num;i++){a.push(true);}
for (i=2;i<=Math.sqrt(num);i++){
for (var j=i*i, coef=0, l=i;j<num-2;coef++){
j = i*i+coef*l-2;
for (i=0;i<a.length;i++){
if (a[i]){a.splice(i,1,i+2);}
return a;

getPrimes(10); // returns [2, 3, false, 5, false, 7, false, 9, false]
// 9 should be false

So as you can see, the algorithm is not catching all the non-prime numbers. Any idea what I've missed? Thanks in advance to anyone who wants to try their hand at it.


You are overwriting the i variable of the outer loop, with the second inner loop for which you also use i. And so the outer loop only runs once.

Use another variable for the inner loop, like k, and you'll get a good result.

But it is not necessary to have that particular inner loop positioned there. It only has to run once really, just before returning. So you could move it out of the main loop.

A minor issue is that your first inner loop goes too far, as j gets incremented in the body of the loop, and the test on j only happens after you have already assigned a value to a[j]. JavaScript just creates that element at that moment, making the array longer, but it would be nicer if you would prevent that from happening

I would also reserve the first 2 indices of array a for representing numbers 0 and 1, just to make your code more readable: then you don't need those +2 and -2 any more.

Taking all this into account, plus some other optimisations, I would suggest this ES6 code:

function getPrimes(num) {
  var a = [...Array(num+1).keys()]; // =[0,1,...,num]
  a[1] = 0; // 1 is not prime
  var rt = Math.sqrt(num); // calculate only once
  for (i=2;i<=rt;i++){
    for (var j=i*i; j<=num; j+=i) a[j]=0;
  return a.filter(Number); // kick out the zeroes
// run it for 30
var a = getPrimes(30); 
// Output