如何提高C ++代码的效率(找到最大的素数)? [英] How to improve the efficiency of c++ code (find the largest prime factor)?

问题描述

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

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;
}

推荐答案

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

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

如果您追求最大质数(如果没有最大质数，则为零)，可以通过重复的整数除法来找到它，类似于UNIX factor程序的许多实现的工作方式，并且:

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

---

还有另一种跳过更多合成的方法，它依赖于以下数学事实:除2和3之外，其他所有质数均采用6n±1 ^(2).

---

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

某些复合材料也具有这种形式，例如25和33，但是您可以在这里降低 small 的效率.

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

虽然更改为使用奇数使原始工作量减少了50％，但又使奇数变体减少了33％:

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

这里的窍门是从5开始，或者在4处增加2:

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)

，您会看到它跳过了第三个奇数(9, 15, 21, 27, ...)，因为它是3的倍数，这是33％进一步减少的原因.您还可以看到素数的误报(在这种情况下，为25和33，但还会更多).

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).

⁽¹⁾您的原始标题要求最大的 even 素数因子和最有效的代码来查找，这将是令人眼花fast乱的:

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

⁽²⁾将任何非负数除以六.如果余数是0、2或4，则它是偶数，因此不是素数(此处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.

如果余数是3，那么它可以被3整除，因此不能是素数(这里是3的特例):

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.

仅剩下余数1和5，这些数字都是6n±1的形式.因此，将2和3作为特殊情况处理，从5开始，并交替添加2和4，您可以保证所有素数(以及少量 复合)将被网捕.

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.

这篇关于如何提高C ++代码的效率(找到最大的素数)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！