# Number of prime numbers between 1 and n

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);


I've created the following performance tests to test the changes: http://jsbin.com/EqiKini/3 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.