How to improve the efficiency of c++ code (find the largest prime factor)?

Question

How to improve the efficiency of this code?

Suppose you have to deal with really big inputs.

‪#‎include‬ <iostream>
using namespace std;
int main()
{   //This program finds out the largest prime factor of given input
    long int n,big=1;
    cin>>n;
    for (long int i=2;i<n;i=i+2)
    {
        if (n%i==0)
           big=i;
    }
    cout<<big;
    return 0;
}

Answer 1

For a start, I don't think the code you have is giving you the largest prime factor anyway, it's simply giving you the largest factor, whether that be prime or composite⁽¹⁾.

If you're after the largest prime factor (or zero if there is none), it can be found by repeated integer division, similar to the way many implementations of the UNIX factor program work, and along the lines of:

def largestPrimeFactor(n):
    if n < 2: return 0            # Special case

    denom = 2                     # Check every denominator
    big = 0
    while denom * denom <= n:     # Beyond sqrt, no factors exist
        if n % denom == 0:        # Check factor, then divide
            big = denom
            n = n / denom
        else:
            denom = denom + 1     # Or advance to next number

    if n > big:                   # What's left may be bigger
        big = n

    return big

---

If you wanted even more efficiency, you can change the way you modify the denominator each time through the loop. Once you've checked two, every other prime must be odd so you could avoid rechecking even numbers, effectively halving the time taken:

def largestPrimeFactor(n):
    if n < 2: return 0            # Special case

    while n % 2 == 0: n = n / 2   # Check and discard twos
    if n == 1: return 2           # Return if it was ALL twos

    denom = 3                     # Check every denominator
    big = 0
    while denom * denom <= n:     # Beyond sqrt, no factors exist
        if n % denom == 0:        # Check factor, then divide
            big = denom
            n = n / denom
        else:
            denom = denom + 2     # Or advance to next odd number

    if n > big:                   # What's left may be bigger
        big = n

    return big

---

There's also another method which skips more composites and it relies on the mathematical fact that, other than 2 and 3, every other prime number is of the form 6n±1⁽²⁾.

Some composites also have this form, such as 25 and 33, but you can wear a small amount of inefficiency here.

While the change to using odd numbers shaved off 50% from the original effort, this one shaves off another 33% from the odd-number variant:

def largestPrimeFactor(n):
    if n < 2: return 0            # Special case

    while n % 2 == 0: n = n / 2   # Check and discard twos
    if n == 1: return 2           # Return if it was ALL twos

    while n % 3 == 0: n = n / 3   # Check and discard threes
    if n == 1: return 3           # Return if it was ALL threes

    denom = 5                     # Check every denominator
    adder = 2                     # Initial value to add
    big = 0
    while denom * denom <= n:     # Beyond sqrt, no factors exist
        if n % denom == 0:        # Check factor, then divide
            big = denom
            n = n / denom
        else:
            denom = denom + adder # Or advance to next denominator,
            adder = 6 - adder     #    alternating +2, +4

    if n > big:                   # What's left may be bigger
        big = n

    return big

The trick here is to start at five, alternately adding two at four:

                      vv         vv        (false positives)
5  7 11 13  17 19  23 25  29 31  35 37  41 ...
    9     15     21     27     33     39   (6n+3, n>0)

and you can see it skipping every third odd number (9, 15, 21, 27, ...) since it's a multiple of three, which is where the 33% further reduction comes from. You can also see the false positives for primes (25 and 33 in this case but more will happen).

---

⁽¹⁾ Your original heading called for the largest even prime factor and the most efficient code for finding that would be the blindingly fast:

if (n % 2 == 0)
    cout << 2 << '\n';
else
    cout << "None exists\n";

(since there's only one even prime). However, I doubt that's what you really wanted.

---

⁽²⁾ Divide any non-negative number by six. If the remainder is 0, 2 or 4, then it's even and therefore non-prime (2 is a special case here):

6n + 0 = 2(3n + 0), an even number.
6n + 2 = 2(3n + 1), an even number.
6n + 4 = 2(3n + 2), an even number.

If the remainder is 3, then it is divisible by 3 and therefore non-prime (3 is a special case here):

6n + 3 = 3(2n + 1), a multiple of three.

That leaves just the remainders 1 and 5, and those numbers are all of the form 6n±1. So, handling 2 and 3 as special cases, start at 5 and alternately add 2 and 4 and you can guarantee that all the primes (and a few composites) will be caught in the net.