CODEWITHSUNDEEP
javascriptmath
David G
David G

Reputation: 96835

How to avoid this bad for loop?

I'm trying to loop through a big number (6 billion to be exact), but I can't because my computer freezes. How can I work my way around this. I'm supposed to find the largest prime factor of 600851475143.

function prime(n) {
    if (n === 1 || n === 2) return false;
    if (n % 2 === 0 || n % 3 === 0) return false;
    return true;
}
var n = 600851475143;
for (var i = 1, c = []; i < n; i++) {
    if ((n % i === 0) && prime(i)) {
        c.push(i);
    }
}

I'm done with it yet. I'm storing the primes in an array.

Upvotes: 0

Views: 128

Answers (2)

MaxArt
MaxArt

Reputation: 22637

That prime function doesn't returns prime numbers only, but all those positive integers that aren't 1 or divisible by 2 and 3.

Let's see the whole algorhythm again. First of all, notice that you don't need to iterate through n, you can stop at its square root (think about it).

var divs = [];
if (!(n & 1)) { // Checking if n is even, using faster bit operators
    divs.push(2);
    while (!(n & 1)) n >>= 1;
}
var d = 3, l = Math.sqrt(n);
while (d < l) {
    if (!(n % d)) {
        divs.push(d);
        while (!(n % d)) n /= d;
        l = Math.sqrt(n);
    }
    d += 2; // No even numbers except 2 are prime, so we skip them
}
if (n !== 1) divs.push(n);

Now divs[divs.length - 1] contains your largest prime divisor of n, and divs all the prime factors.

Upvotes: 1

sachleen
sachleen

Reputation: 31141

Your prime() function doesn't do what the name says it should. There are many efficient ways of factoring primes, try this one for example:

var x = 600851475143;
var i = 2;
var sk;
while(i <= x) 
{
    while (x % i == 0)
    {
        sk = i;
        x = x / i;
    }
    i++;
}
console.log(sk);

Output: 6857

This page has another (view source) function for factoring.

Upvotes: 2

Related Questions