c++ - 程序不运行，工作量太大？

Question

当我运行它时，它只是打开命令提示符窗口，只有下划线在开始时闪烁。我等了 20 分钟，什么也没发生，没有文字/错误。

#include <iostream>

using namespace std;

int prime(unsigned __int64 para) {          // returns 1 if para is a prime number
    for (unsigned __int64 i = 2; i < para; i++) {
        if (para % i == 0) {
            return 0;
        }
    }
    return 1;  
}

int main()
{
    for (unsigned __int64 i = 300851475143; i > 2; i--) {
        if (prime(i) == true) {                  //  checks if i is prime
            if (600851475143 % i == 0) {         //  checks if 600851475143 is divisible by said prime, print it if so
                cout << i << endl;
                break;

            }
        }
    }
}

Answer 1

该程序的复杂性是巨大的——它需要很长时间才能运行。它可能是有效的，但for循环中的迭代次数非常巨大。

您正在尝试运行此循环：

for (unsigned __int64 i = 300851475143; i > 2; i--)

仅此一项就太大了，程序无法快速完成。

除此之外，在prime()您运行第二个循环时：

for (unsigned __int64 i = 2; i < para; i++)

其中（因为para与i外循环相关）使得复杂度 O(n^2)

Answer 2

您知道这300851475143是一个巨大的数字，并且您有两个围绕这个数字工作的嵌套循环！

如果每次迭代都需要1ns您300s x 300s = 25 hours完成工作。（这只是一个近似值）