javascript - What function does Math.sqrt(n) serve in relation to Eratosthenes algorithm for finding N primes? -

did word title correctly?

var eratosthenes = function(n) {     // eratosthenes algorithm find primes under n     var array = [], upperlimit = math.sqrt(n), output = [];     // make array 2 (n - 1)     (var = 0; < n; i++)          array.push(true);     // remove multiples of primes starting 2, 3, 5,...     (var = 2; <= upperlimit; i++) {         if (array[i]) {             (var j = * i; j < n; j += i)                  array[j] = false;         }     }     (var = 2; < n; i++) {         if(array[i])             output.push(i);     }     return output; } 

fiddle: http://jsfiddle.net/karzw/

what purpose of upperlimit = math.sqrt(n)?

code from: sieve of eratosthenes algorithm in javascript running endless large number

the largest possible factor of number it's square root.

take 17. prime? naively factors 1...17 or take square root , 2-4, because after 4, there aren't new possible factors left.

to put little more detail it.

let's through naive model (yes, numbers don't need checked, because know it's not even, naive):

is 17 divisible 2?  no 17 divisible 3?  no 17 divisible 4?  no  17 divisible 5?  no 17 divisible 6?  no 17 divisible 7?  no  .... 17 divisible 16?  no  

17 prime.

now, let's use upper bound of square root.

is 17 divisible 2?  if was, 2 x 8 or 2 x 9. 17 divisible 3?  if was, 3 x 5 or 3 x 16. 17 divisible 4?  if was, 4 x 4 or 4 x 5. 

now happens when 5? you've transposed factors.

is 17 divisible 5? if was, 5x3 or 5x4. well, covered "is 17 divisible 3" , "is 17 divisible 4"

the same pattern repeats end of naive model.

so, once you've checked possible factors square root of number, you've checked possible factors number.