c - 我怎样才能提高我的代码的效率？

Question

我想让我的程序找到数字 600851475143 的最大质因数。例如，13195 的质因数是 5、7、13 和 29，其中最大的是 29。虽然我的代码确实有效，但即使对于更小的输入，例如 6kk(大约需要 15 秒。对于 12kk，它需要 37 秒，所以增量甚至比线性增量更差)，答案需要很长时间才能出现，这是 100k 倍小于我应该用作输入的数字。下面是我的代码，任何有关提高代码效率的帮助将不胜感激。

#include <stdio.h>
#include <math.h>

int main()
{
    long long int number=600851475143;
    int largest_prime_factor,i,j,k;
    for (i=1;i<number/2;i+=2){
         k=0;
         j=3;
         for (j=3;j<=sqrt(i);j+=2){
            if (i%j==0){
                k++;
                break;
              }
                }
        if (k==0){
            if (number%i==0)
                largest_prime_factor=i;
        }
    }
    printf("The largest prime factor of 600851475143 is: %d",  
    largest_prime_factor);
    return 0;
}

Answer 1

您无需浏览整个列表。一旦找到一个质因数，您就可以用它对您的数字进行因式分解，然后继续处理剩下的数。

例如，以您的示例为例:600,851,475,143。您可以很快找到它的第一个质因数是 71。如果您将 600,851,475,143 除以 71，您将得到 8,462,696,833。除了 71 之外，这两个数字都具有相同的质因数。因此，现在您可以搜索原始数的最大因数，但搜索空间减少了 2 个数量级。

另外，请注意，如果数字本身是质数，您的代码将失败。要解决这个问题，请将您的最大数量初始化为

int largest_prime_factor = 1;

如果最后还是1，则返回数字本身。 (您可以使用 number 进行初始化，但您很快就会明白我为什么选择 1)

因此首先将 2 视为特例:

    long long remain = number;
    while (remain % 2 == 0) {
            remain /= 2;
            largest_prime_factor = 2;
    }

然后在你的循环中做类似的事情。由于对于素数，我们只需要检查其平方根，因此我们将循环限制为两种情况，具体取决于我们是否仍认为该数可能是素数。

1. 仍然是质数:测试到 sqrt(number)
2. 不再是素数:测试直到最大因子超过剩余的数。

最后，你修改后的代码可能是这样的:

#include <stdio.h>

int main()
{   
    long long int number=600851475143;
    long long largest_prime_factor = 1,i,j,k;
    long long remain = number;

    while (remain % 2 == 0) {
        remain /= 2;
        largest_prime_factor = 2;
        /* Uncomment to see the factors 
           printf("2 ");*/
    }   

    for (i=3; (largest_prime_factor == 1 && i*i <= number) ||  
            (largest_prime_factor > 1&& i <= remain); i+=2){
        k=0;
        j=3;
        for (j=3; j*j<=i;j+=2){
            if (i%j==0){
                k++;        
                break;   
            }        
        }
        if (k==0 && remain%i==0) {
            largest_prime_factor=i;
            while (remain % i == 0) {
                /* Uncomment to see the factors 
                printf("%d ", i); */
                remain /= i;  
            }            
        }
    }
    printf("The largest prime factor of %Ld is: %Ld",
            number, largest_prime_factor);
    return 0;
}  

另请注意，其他变量也应为(long long)类型。

瓶颈在于检查每个数字是否为素数，如果素数本身很大，整个过程仍然会很慢。但是你可以获得更快的平均情况。对于您的示例，该算法在不到一秒的时间内得到因子 71、839、1471 和 6857。