c++ - 为什么我的程序不能处理大数？

Question

我正在尝试编写一个程序来查找 600851475143 的最大质因数。它可以完美地处理较小的数字(直到 10000)，但仅此而已。我该如何改变它？该程序不会给出任何错误或自行结束，只是不会输出任何内容。

#include <iostream>
#include <vector>
using namespace std;

bool isPrime( unsigned long long int num);


int main() {
    unsigned long  long int  m = 600851475143;
    std::vector<int> pfactors;
    pfactors.reserve(100000000);
    for (long long int  i = 2; i <= m; i++) {
         if (isPrime(i) == true) {
             if (m % i == 0) {
                 pfactors.push_back(i);
             }
        }
      }
    for (vector<int>::iterator it = pfactors.begin(); it != pfactors.end(); it++) {
        cout << *it << endl;
    }
    cin.get();
    return 0;
    }




bool isPrime(unsigned long long int num)
{
    if (num < 2) 
        return false;


    if (num > 2 && (num % 2) == 0)
        return false;


    for (unsigned long long int i = 2; i < num; i++)
    {

        if ((num % i) == 0) 
        {

            return false; 
        }
    }


    return true; 
}

Answer 1

@DanyalImran 和@Jean-FrançoisFabre 提供的答案都不正确。巧合的是，600851475143 是 71、839、1471 和 6857 的乘积，并且所有除数都小于 sqrt(num)。如果 OP 中的数字是 600851475149(质数)怎么办？

因此我们需要搜索整个范围 [2,num]，而不是范围 [2,sqrt(num)]。

因此，这是我在尝试使用埃拉托色尼筛法预先计算素数标志 vector 并记住之前找到的素数来优化搜索后得到的结果。

尽管 Eratosthenes 筛法确实是在某个指定范围内找到所有素数的最快方法(它没有除法运算，只有比除法快几倍的乘法运算)，但这种方法没有太大帮助，因为它没有消除需要遍历 vector 以找到标记为素数的元素，然后将有问题的数字除以找到的素数(我在@Jean-FrançoisFabre 的实现中故意将 vector<bool> 替换为 vector<char> 以避免可能的“位压缩”在 vector 计算中将 vector<bool> 作为位位置的实现肯定比字符位置计算更昂贵)。

我用这种方法解决 150212868857 素数 OP 中的任务的时间是 ~7:05 分钟，在我的 1.4GHz AMD 上:

150212868857

real    7m5.156s
user    7m5.063s
sys 0m0.008s

试图记住所有以前找到的素数以加速 isPrime()测试更糟，所以我没有给它完成的机会。这解释了同样需要遍历素数 vector ，并且由于要从内存中读取的数据量，它甚至更加昂贵。

最终变体只是候选除数在 3 到 num 范围内的迭代使用步骤 2 并调用 isPrime仅当 num甚至是候选人。这种方式显示的时间和之前的一样加减几秒。因此，只要所使用的数学适合现代 CPU 的 native 寄存器，访问 vector 元素似乎就和除法一样昂贵。

但是，当所讨论的数字不是质数时(如在 OP 中)，仍有优化空间可以缩短搜索时间。

代码:

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

//#define SIEVE
vector<char> primeFlagger;

void initSieve(unsigned long long int limit) {
    unsigned long long int root = (unsigned long long int)(sqrt(limit));
    primeFlagger = vector<char>(root+1,true);
    primeFlagger[0] = primeFlagger[1] = false;

    for(unsigned long long int j=2; j<=root; j++)
    {
        if(primeFlagger[j])
        {
            for(unsigned long long int k=j; (k*j)<=root; k++)
            {
                primeFlagger[j*k]=false;
            }
        }
    }
}

#ifdef SIEVE
bool isPrime(unsigned long long int num)
{
    if (num <= 2)
        return true;

    if ((num % 2) == 0)
        return false;

    unsigned sqr = (unsigned)sqrt(num);
    for(unsigned i = 3; i <= sqr; i+=2) {
        if (primeFlagger[i] && num % i == 0)
            return false;
    }

    return true;
}
#else
bool isPrime(unsigned long long int num)
{
    if (num <= 2)
        return true;

    if ((num % 2) == 0)
        return false;

    unsigned sqr = (unsigned)sqrt(num);
    for(unsigned i = 3; i <= sqr; i+=2) {
        if (num % i == 0)
            return false;
    }

    return true;
}
#endif

int main() {
    unsigned long long int  m = 600851475143;//150212868857;//600851475149;
    std::vector<unsigned long long int> pfactors;

#ifdef SIEVE
    initSieve(m);
#endif

    if (m % 2 == 0) {
        do {
            m /= 2;
        } while (m % 2 == 0);
        pfactors.push_back(2);
    }

    for (long long int i = 3; i <= m; i+=2) {
        if (m % i == 0 && isPrime(i)) {
            do {
                m /= i;
            } while (m % i == 0);
            pfactors.push_back(i);
        }
    }

    for (vector<unsigned long long int>::iterator it = pfactors.begin(); it != pfactors.end(); it++) {
        cout << *it << endl;
    }

    return 0;
}

OP 中带有数字的结果:

$ g++ -O3 prime1.cpp
$ time ./a.out 
71
839
1471
6857

real    0m0.004s
user    0m0.002s
sys 0m0.002s