4
\$\begingroup\$

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]);
}
\$\endgroup\$
5
\$\begingroup\$

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);
  }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Rafael Adel Oct 16 '11 at 22:47
  • \$\begingroup\$ @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. \$\endgroup\$ – Guffa Oct 17 '11 at 7:27
  • \$\begingroup\$ 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. \$\endgroup\$ – Rafael Adel Oct 17 '11 at 8:15
  • \$\begingroup\$ @Rafael: I see a big difference: jsperf.com/sieve-versions \$\endgroup\$ – Guffa Oct 17 '11 at 8:26
  • \$\begingroup\$ mmmm, maybe it's just my computer. I don't really know, i'll try it again though. Thanks :) \$\endgroup\$ – Rafael Adel Oct 17 '11 at 8:50
0
\$\begingroup\$

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]
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Evil Jul 18 '16 at 4:25
  • \$\begingroup\$ @Evil What was faster for you, prime[i] = true; or prime.push(true); ? For me prime.push(true); \$\endgroup\$ – MrHIDEn Aug 15 '16 at 6:16
  • \$\begingroup\$ 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. \$\endgroup\$ – Evil Aug 15 '16 at 6:23
  • \$\begingroup\$ var max = Math.sqrt(n) | 0 is a good idea, I do not remember I tested it, but I believe I did. \$\endgroup\$ – MrHIDEn Aug 15 '16 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.