Largest prime factor function 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 &lt;= 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 &lt; i; k++) {
        if (i % k == 0) {
            return false;
        }       
    }
    return true;
}
}

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

document.write(largestPrime(600851475143));
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 &lt;= n; c += 2) {
        if (n % c == 0) {
            largest = c;
            do {
                n /= c;
            } while (n % c == 0);
        }
    }
    // Wrong: return largest == 0 ? x : largest;
    return n &gt; 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 &lt;= 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 &lt;= 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.