如何提高这段代码的效率?
假设你必须处理非常大的输入。
#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;
}
首先，我认为你的代码并没有给出最大的素数因子，它只是给出了最大的因子，无论是素数还是合数(1) 。
如果您在寻找最大的素数因子(如果没有，则为零)，则可以通过重复整数除法找到它，类似于UNIX factor程序的许多实现的工作方式，并沿着以下行:
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
如果你想要更多的效率，你可以改变每次在循环中修改分母的方式。一旦你检查了2，其他质数必须是奇数，这样你就可以避免重新检查偶数，有效地减少了一半的时间:
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
还有一种方法，它跳过了更多的合数，它依赖于一个数学事实，即除了2和3之外，其他质数都是6n±1 (2)的形式。
一些复合材料也有这种形式，如25和33，但您可以在这里使用少量低效率。
虽然使用奇数的变化减少了原始工作量的50%，但这一个从奇数变体中减少了另外33%:
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
这里的技巧是从5开始，在4处交替加2:
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)
，你可以看到它跳过每三个奇数(9, 15, 21, 27, ...)，因为它是3的倍数，这就是33%进一步减少的来源。您还可以看到素数的假阳性(在本例中为25和33，但会发生更多)。
(1)您的原始标题需要最大的偶数素数因子，而查找它的最有效代码将是快得令人眼花的:
if (n % 2 == 0)
cout << 2 << 'n';
else
cout << "None existsn";
(因为只有一个偶数素数)。然而，我怀疑这是不是你真正想要的。
(2)任意非负数除以6。如果余数为0、2或4，则它是偶数，因此是非素数(2是这里的特殊情况):
6n + 0 = 2(3n + 0), an even number.
6n + 2 = 2(3n + 1), an even number.
6n + 4 = 2(3n + 2), an even number.
如果余数是3，那么它可以被3整除，因此是非素数(3是这里的特殊情况):
6n + 3 = 3(2n + 1), a multiple of three.
只剩下余数1和5，这些数字都是形式6n±1。因此，处理2和3作为特殊情况，从5开始，交替添加2和4，您可以保证所有素数(以及几个组合)将被捕获。