如何提高c++代码的效率（求最大质因数）？

Question

如何提高这段代码的效率？

假设您必须处理非常大的输入。

‪#‎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

首先，我认为您的代码并没有给您最大的素数因子，它只是给您最大的因子，无论是素数还是素数复合⁽¹⁾.

如果你在最大的质因数之后（如果有 none 则为零），可以通过重复整数除法找到它，类似于 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

如果你想要甚至更高的效率，你可以通过循环改变每次修改分母的方式。一旦你检查了两个，其他每个素数都必须是奇数，这样你就可以避免重新检查偶数，有效地将所花费的时间减半：

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⁽²⁾.

有些复合材料也有这种形式，比如25和33，但是你可以在这里穿小量低效

虽然使用奇数的变化比原来的努力减少了 50%，但这个从 odd-number 变体中又减少了 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

这里的诀窍是从五开始，在四时交替加二：

                      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, ...)，因为它是三的倍数，这就是 33% 进一步减少的来源。您还可以看到素数的误报（在这种情况下为 25 和 33，但还会发生更多）。

⁽¹⁾ 您的 original 标题要求最大的 even 素数和找到它的最有效代码将是令人眼花缭乱的速度：

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

（因为只有一个偶素数）。但是，我怀疑那是你真正想要的。

⁽²⁾ 将任何 non-negative 数除以六。如果余数是 0、2 或 4，那么它是偶数，因此 non-prime（这里 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 整除，因此 non-prime（这里 3 是一个特例）：

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

只剩下余数 1 和 5，这些数字都是 6n±1 的形式。因此，将 2 和 3 作为特殊情况处理，从 5 开始并交替添加 2 和 4 并且您可以保证所有素数（和很少个组合）会被网捕获。

如何提高c++代码的效率（求最大质因数）？

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

c++

algorithm

mathematical-optimization