C 找出大数的质因数

Question

我写了下面的 C 代码来找出一个大数的最大引物因子，我的程序在运行时一直在执行。我试图通过分配 2^32 范围内的 iBigNum 来调试它-1，然后它起作用了。

LONG64 iBigNum = 600851475143,iCurr=0,iLarge=0;
    //600851475143 
    /*4294967295
      4000000000
    */iCurr = iBigNum-1;
    while(iCurr > 0 )
    {
        if(iBigNum % iCurr == 0){
            iLarge=iCurr;
            break;
        }
        iCurr--;
    }
    MsgPrintf(TEXT("CustomPrint"),TEXT("%d"),iLarge);

之间，LONG64定义为basetsd.h

//
// The following types are guaranteed to be signed and 64 bits wide.
//

typedef __int64 LONG64, *PLONG64;

我正在运行频率为 3.16GHz 的 Intel Core 2 Duo CPU 和 4 GB RAM 上运行代码。这是预期的行为吗？有人能给我指明方向吗？谢谢

Answer 1

从头开始似乎是个好主意，因为您需要找到最大的因素，但事实并非如此。最小的可能因子是 2，因此最大的可能因子是 n/2。您花费了第一个 n/2，即 300425737571 次迭代是徒劳的。你的情况更糟，因为最小的因子是 17。

不要自作聪明。从底部开始分解。当您找到一个因子时，将您的数字除以它，可能多次，然后存储最后一个因子。当您的数字为 1 时停止。

(如果你的数字是素数的平方，这种天真的方法仍然很糟糕，但平均而言，如果你只检查一个数字，它应该相当快。)

编辑:下面是将按照我上面描述的方式找到最大因素的代码。它在非质数上运行得相当快，但在我的机器上运行一个大质数 (479001599) 大约需要 4 秒。 OP 的原始输入是其 1,000 多倍。

有了这个警告，这里是:

LONG64 max_fact(LONG64 iBigNum)
{
    LONG64 maxFact = 1;
    LONG64 i = 2;

    while(iBigNum > 1)
    {
        while (iBigNum % i == 0){
            iBigNum /= i;
            maxFact = i;
        }
        if (i == 2) i = 3; else i += 2;
    }

    return maxFact;
}