# Sieve of Eratosthenes in JavaScript

I found this method kinda tough to get for a beginner like me, but I tried to do my best, and here's what I came up with.

Is this good code regarding performance? Is there anything wrong with it?

var notPrime = [] ;
var prime = [] ;

var n = prompt("Enter n: ");

for(var i = 2 ; i < n ; i++ ){

if(notPrime.indexOf(i) != -1){
continue;
}

for(var j = i ; i <= j ; j++){
if((i * j) < n){
notPrime.push(i*j);
} else {
break;
}
}
prime.push(i);
}

for(var f in prime){
console.log(prime[f]);
}


Lets say that there is room for improvement. ;)

The prompt method returns a string, but you want a number, so you should parse the string:

var n = parseInt(prompt("Enter n: "), 10);


Using indexOf on an array is slow. Instead of putting all the non-primes in a bucket and rummaging through it, you should use an array containing boolean values where the index is the number and the values tells you if it's a prime or not.

Accessing an array by index is an O(1) operation, while searching for a value in an array is an O(n) operaton. As n grows, this code will get slower and slower the longer you let it run.

As you are pushing a lot of duplicate non-primes in the array, an array of boolean values will actually use about 70% less memory eventhough the primes also takes up space in it.

This loop is pretty pointless:

for(var j = i ; i <= j ; j++){


The condition will never be false. You should instead use the i * j < n condition to break out of the loop:

for(var j = i; i * j < n; j++){
notPrime[i * j] = true;
}


### Edit:

You are still using the array as a kind of collection. You should set all values to true at start, and then set all non-primes to false. This code (based on the algorithm here) is about five times faster:

var n = parseInt(prompt("Enter n: "), 10);
var i, j;
var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;

for (i = 2; i * i < n ; i++) {
if (prime[i]) {
for (j = 0; i * i + i * j < n ; j++) {
prime[i * i + i * j] = false;
}
}
}

var cnt = 0;
for (i = 2 ; i < n ; i++) {
if (prime[i]){
console.log(i);
}
}

• Thanks .. The array of boolean values note really helped. It accelerate the whole process, eg: finding primes in from 0 to 20000 with the old code hangs the browser. But with the boolean values it works great. Thanks – Rafael Adel Oct 16 '11 at 22:47
• @Rafael: You are still using the array as a kind of collection. You should use the value in the array instead of checking for the existance of items. See the code added above. – Guffa Oct 17 '11 at 7:27
• mmmm, i tried the code you wrote. I'm afraid i don't notice a big difference, it's actually the same as the one i edited it. – Rafael Adel Oct 17 '11 at 8:15
• @Rafael: I see a big difference: jsperf.com/sieve-versions – Guffa Oct 17 '11 at 8:26
• mmmm, maybe it's just my computer. I don't really know, i'll try it again though. Thanks :) – Rafael Adel Oct 17 '11 at 8:50

I made some improvements and speed up this code.

var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;


replaced by 2x faster

var prime = [];
for (i = 0; i <= n ; i++) prime.push(true);


for (i = 2; i * i < n ; i++) {


i * i is calculated every time, replaced by

for (var i = 2; i <= Math.sqrt(n)|0; i++) {


Math.sqrt(n)|0 reduces unneeded calculations

for (j = 0; i * i + i * j <= n ; j++) {
prime[i * i + i * j] = false;


Here are so many calculations iterated every time. I reduced them to:

for (var j = i*i; j <= n; j += i) {
prime[j] = false;


function sieve5(n) {
var i,j;
// true-table
var prime = [];
for (i = 0; i <= n; i++) prime.push(true); // mark 'numbers' 0..n as 'true'

// mark for swipe
for (i = 2; i <= Math.sqrt(n)|0; i++) {
if (prime[i]) {
for (j = i*i; j <= n ;j += i) {
prime[j] = false; // eliminate all none prime numbers and mark them as 'false'
}
}
}

// extract primes
var primes = [];
for (i = 2; i <= n; i++) { // 'zero' and 'one' is not prime
if (prime[i]) primes.push(i) // get all primes from 2..n
}

return primes;
}
console.time("sieve5");
primes = sieve5(1000000);// 62ms on my PC
console.timeEnd("sieve5");
console.log('length=',primes.length);

primes = sieve5(100);
console.log(primes);
// [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
console.log(sieve5(11));//[2,3,5,7,11]

• I do not totally get why downvote. The code improvements are good, left alone without pushes gives more than twice speedup. And the killer comes from push. Funny thing - alone push test in Firefox is faster than loop (fill also), on Chrome oposite, but sieve5 consistently outperforms other sieves. +1 from me. – Evil Jul 18 '16 at 4:25
• @Evil What was faster for you, prime[i] = true; or prime.push(true); ? For me prime.push(true); – MrHIDEn Aug 15 '16 at 6:16
• prime.push(true) on Firefox, prime[i] = true on Chrome, I have tried with prime.fill(true) but this is a bit of lottery. Also I tried with things like to store Math.sqrt(n) | 0 to a variable, but it gives neglible saving. – Evil Aug 15 '16 at 6:23
• var max = Math.sqrt(n) | 0 is a good idea, I do not remember I tested it, but I believe I did. – MrHIDEn Aug 15 '16 at 6:40