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;
}
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(1).
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(2).
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).
(1) 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.
(2) 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.