Massive for loop taking too long to load

Question

I'm working on a program designed to generate prime numbers, and I'm trying to find the 10001st prime number. Each time the loop runs, it tests variable i to see if it's divisible by variable j, which is part of another loop that goes up to half of i. If i is divisible by j then it adds one to variable prime, and when the loop's done it checks to see if variable prime is larger than two; if it is, then i is not prime. If it is prime, it gets push()ed to the variable array, which stores all the primes. Sorry if that's a little confusing.

My problem is that although this code works, whenever I set the first for loop too high (here I have it end at 100000), my browser freezes:

var prime = 0;
var array = [];
for(var i = 2; i <= 100000; i+=1) {
  var prime = 0;
  for(var j = 0; j <= i/2; j+=1) {
    if(i % j === 0) {
      prime += 1;
    }
  }

  if(prime < 2) {
    array.push(i);
  }
}

console.log(array.length)

I know I could just copy and paste all the prime numbers but I want to make the program work. Any ideas to make the program stop freezing?

The algorithm you're using is just too inefficient. There's not much you can do other than use a better algorithm. — JJJ, Apr 08 '15 at 19:08
Possible duplicate of http://stackoverflow.com/questions/1160137/execute-background-task-in-javascript — cybersam, Apr 08 '15 at 19:11
use square root method to solve. so number of iteration will be reduced — Prashant, Apr 08 '15 at 19:11
Try implementing this algorithm http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ..Its quick, and an example of dynamic programming — Sailesh Kotha, Apr 08 '15 at 19:12
Ok, I take back what I said. You can make this 10 times faster if you add `if( prime === 2 ) break;` inside the inner loop. http://jsfiddle.net/reumzot5/ — JJJ, Apr 08 '15 at 19:12
Why go all the way to `i/2`? You can stop at `Math.sqrt(i)`. Also, you can skip all even values of `j`. Also, why does `j` start at 0? Start at 3 instead. Also, your loop keeps going after a prime factor has already been found, use `break` instead. — Austin Mullins, Apr 08 '15 at 19:13
Check [this answer](http://stackoverflow.com/a/12287599/1585868) for a better faster solution. — leigero, Apr 08 '15 at 19:17

score -1 · Accepted Answer · answered Apr 08 '15 at 19:33

This is because the time complexity of your algorithm is pretty much O(n^2). Sieve of Eratosthenes created a better algorithm that will prevent your browser from freezing. Here is one way of doing it:

var exceptions = {
  2: 2,
  3: 3,
  5: 5,
  7: 7
}

var primeSieve = function (start, end) {
  var result = [];
  for (start; start < end; start++) {
    if (start in exceptions) result.push(start);
    if (start > 1 && start % 2 !== 0 && start % 3 !== 0 && start % 5 !== 0 && start % 7 !== 0) {
      result.push(start);
    }
  }
  return result;
};

You can obviously make this look prettier, but I just did it quickly so you can get the point. I hope this helps! Let me know if you have further questions.

Massive for loop taking too long to load

1 Answers1