Largest prime factor function

Question

I have written a function which finds the largest prime factor of some number. This function works but the problem is that it is too slow. For instance, when I enter 600851475143 as a parameter, the process of finding largest prime factor lasts too long. How can I modify it so that it works faster?

class test {

static addArray(someArray, member) {
    for (var i = 0; i <= someArray.length; i++) {
        if (i == someArray.length) {
            someArray[i] = member;
            return someArray;
        }
    }
}
static someLength(someArray) {
    var i = 0;
    while (someArray[i] !== undefined) {
        var lastItem = i;
        i++;
    }
    return i;
}
static testPrime(i) {
    for (var k=2; k < i; k++) {
        if (i % k == 0) {
            return false;
        }       
    }
    return true;
}
}

var primeArray = [];
function largestPrime(n) {
    for (var i=2; i < n; i++) {
        //var k = n / i;
        if (n % i == 0 && test.testPrime(i) == true) {  
            test.addArray(primeArray, i);
            n == n / i;
        }
    }
    return primeArray[test.someLength(primeArray) - 1];
}

document.write(largestPrime(600851475143));

Answer 1

The algorithm can be improved. I took the liberty to use my existing Java, also as Python might be somewhat slower.

On the Python code: X == true should simply be X.

long largestPrimeFactor(long x) {
    long largest = 0;
    long n = x; // Remaining number where factors divided out.
    if (n % 2 == 0) {
        largest = 2;
        do {
            n /= 2;
        } while (n % 2 == 0);
    }
    for (int c = 3; c*c <= n; c += 2) {
        if (n % c == 0) {
            largest = c;
            do {
                n /= c;
            } while (n % c == 0);
        }
    }
    // Wrong: return largest == 0 ? x : largest;
    return n > 1 ? n : largest;
}

The loop searching for factors handles 2 before the loop and then loops from 3 with steps of 2.

    for (int c = 3; c*c <= n; c += 2) {

In every loop step, if c is a factor of n, n is divided by c as often as possible. In fact n has no longer smaller factors than c.

Hence c is a prime, and in fact the largest found prime upto then.

If after the loop no largest prime was found, the parameter itself is a prime.

As n in every step is divided by all smaller factors, you need only to loop while c <= n / c holds: the second c being the smallest co-factor of n for c. Together with += 2 this hugely decreases the number of steps.

Your extra test on the factor being prime is the largest slow-down, as it does not exploit the factor filtering till then.

Answer 2

[Ported from SO]

Alright, before we go into that, let's get a little bit of theory sorted. The way you measure the time a particular piece of code takes to run is, mathematically, denoted by the O(n) notation (big-o notation) where n is the size of the input.

Your test prime function is of something called linear complexity meaning that it'll become linearly slow as the size of n (in this case, your number input) gets large.

For the number 15, the execution context is as follows:

15 % 2 == 0 (FALSE)
15 % 3 == 0 (TRUE)
...
15 % 14 == 0 (FALSE)

This means that for the number 100, there will be 98 (2 - 99) steps. And this will grow with time. Let's take your number into consideration: 600851475143. The program will execute 600851475143; the for-loop will get triggered 600,851,475,141 times.

Now, let's consider a clock cycle. Say each instruction takes 1 clock cycle, and a dumbed down version of your loop takes 2, the number 600851475143 will execute 1,201,702,950,286 times. Consider each clock cycle takes 0.0000000625 seconds (for a 16-MHz platform such as the Arduino), the time taken by that code alone is:

0.0000000625 * 1201702950286 = ~75,106 seconds

Or around 20 hours.

You see where I am going with this.

Your best best to get this program to work faster is to use a probabilistic test and confirm your findings using this number (or a BigInteger variant thereof).

---

Your approach is more linear, in the sense that the number of iterations for the for-loop to check for primality increases with an increasing number. You can plot the CPU cycle time along with the number and you'll realize that this is a rather inefficient way to do this.

I have discrete mathematics at my Uni, so just a word of warning - primality tests and their variants get really messy as you get into the utopia of faster and faster tests. It's a path filled with thorns of mathematics and you should have a seat belt while riding through the jungle! ;)

If you need more information on this, I would be glad to assist! I hope this helped! :)