0

Did I word that title correctly?

var eratosthenes = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];
    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) 
        array.push(true);
    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) 
                array[j] = false;
        }
    }
    for (var i = 2; i < n; i++) {
        if(array[i])
            output.push(i);
    }
    return output;
}

fiddle: http://jsfiddle.net/KARZw/

What is the purpose of upperLimit = Math.sqrt(n)?

code from: Sieve of Eratosthenes algorithm in JavaScript running endless for large number

Community
  • 1
  • 1
eveo
  • 2,797
  • 15
  • 61
  • 95

2 Answers2

3

The largest possible factor of a number is it's square root.

Take 17. Is that prime? You could naively look for all factors from 1...17 or you could take the square root and look from 2-4, because after 4, there really aren't any new possible factors left.

To put a little more detail into it.

Let's look through the naive model (yes, the even numbers don't need to be checked, because we know it's not even, but this is very naive):

Is 17 divisible by 2?  No
Is 17 divisible by 3?  No
Is 17 divisible by 4?  No 
Is 17 divisible by 5?  No
Is 17 divisible by 6?  No
Is 17 divisible by 7?  No 
....
Is 17 divisible by 16?  No

17 is prime.

Now, let's say that you use the upper bound of the square root.

is 17 divisible by 2?  If it was, it would be 2 x 8 or 2 x 9.
is 17 divisible by 3?  If it was, it would be 3 x 5 or 3 x 16.
is 17 divisible by 4?  If it was, it would be 4 x 4 or 4 x 5.

Now look what happens when you get to 5? You've basically just transposed the factors.

Is 17 divisible by 5? If it was, it would be 5x3 or 5x4. Well, those were already covered by "is 17 divisible by 3" and "Is 17 divisible by 4"

The same pattern repeats up to the end of the naive model.

So, once you've checked all the possible factors up to the square root of the number, you've checked all the possible factors for the number.

Brian Hoover
  • 7,861
  • 2
  • 28
  • 41
  • Awesome, thanks. Can't say I understand the math behind it though. Isn't the highest factor of a prime number the number itself? Like for example 17, it's just 1 and 17, so why square it? – eveo Jul 11 '13 at 16:30
  • A prime is defined by having 2 factors, itself and 1. What the algorithm is doing is removing all items that are definitively non-prime, and the outer loop only has to go up to the square root of the upper limit to filter those out. – Brian Hoover Jul 11 '13 at 16:46
  • 1
    [A Proof](http://www.proofwiki.org/wiki/Composite_Number_Has_Prime_Factor_Less_Than_Or_Equal_To_Its_Square_Root). – Enigmadan Jul 11 '13 at 16:52
1

The square root of a number is the largest possible member of a pair of its prime factors.

Any prime factor larger than the square root will need to be multiplied by a prime factor smaller than the square root to get the number.

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964