7
\$\begingroup\$

I came up with the following solution to find the number of prime numbers from 1 to n.

I'm wondering if there is a more optimal way.

var max = 10;
var compositeNumbers = {};

mainLoop:
for (var i=2; i<= max;i++) 
{
  smallLoop:
   for (var j=2; j<=Math.ceil(Math.sqrt(i));j++)
   {
      if (i % j == 0)
      {
          compositeNumbers[i]=1;
          continue mainLoop;
      }
   }

}


console.log(max - Object.keys(compositeNumbers).length);
\$\endgroup\$
0
4
\$\begingroup\$

I've created the following performance tests to test the changes: http://jsbin.com/EqiKini/3

enter image description here

I'm going to start out this review by pointing out your algorithm is slightly off! Take a look at compositeNumbers after your code above and you'll see it is: {2: 1, 4: 1, 6: 1, 8: 1, 9: 1, 10: 1}. Clearly 2 is not composite but it will normally work because you exclude 1. The way I would address this is by doing a check if max is less than 3.

function findNumPrimes(max) {
  if(max <= 1) return 0;
  var compositeNumbers = {1: 1}; //1 is composite
  //if (max > 3) {//in retrospect no need for this pre condition as it will be handled by the loop
  mainLoop: for (var i = 4; i <= max; i++) {
    smallLoop: for (var j = 2; j <= Math.ceil(Math.sqrt(i)); j++) {
      if (i % j === 0) {
        compositeNumbers[i] = 1;
        continue mainLoop;
      }
    }
  }
  return max - Object.keys(compositeNumbers).length;
}

As you'll notice I slightly adapted your code so you would use it like console.log(findNumPrimes(10000)); //1229

The first notable (and obvious) speed improvement I'll point out is you should probably cache Math.ceil(Math.sqrt(i)) in a variable (2 times + speed improvement for max > 100).

An even better implementation would probably make use of the ideas from the Sieve of Eratosthenes. I added a case to the performance tests using the sieve find prime number algoritm posted here.

\$\endgroup\$

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.