0
\$\begingroup\$

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));
\$\endgroup\$
  • \$\begingroup\$ Hmm, is n == n / i; your problem? This statement does nothing, I think you meant n=n/i; \$\endgroup\$ – user181660 Oct 10 '18 at 13:15
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your largestPrimeFactor(6) returns 2 instead of 3. Calculating c * c on every loop iteration could be avoided if you adjust the upper limit accordingly. This could also speed up the special case where n is the square of a prime. \$\endgroup\$ – aventurin Oct 10 '18 at 21:27
  • \$\begingroup\$ @aventurin the return did not take into account the remaining factor n. And indeed (c+2)² = c²+4c+4 so starting with int cSquare = 3*3; and at every step adding (c + 1) << 2. Thanks. \$\endgroup\$ – Joop Eggen Oct 10 '18 at 22:13
-1
\$\begingroup\$

[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! :)

\$\endgroup\$
  • \$\begingroup\$ We have lots of advice on this site about factoring 600851475143 that does not involve anything fancy like probabilistic primality tests. It's all about choosing the right strategy. \$\endgroup\$ – 200_success Sep 9 '18 at 19:19
  • \$\begingroup\$ The main focus on making him understand why his code was inefficient. You can use what you mention about choosing your strategy, but considering the theory isn't where it is speed to be, any shining answer night not make sense. Further, a probabilistic test is the fastest. \$\endgroup\$ – weirdpanda Sep 9 '18 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.