c++ - 有没有办法在 C++ 中分解大数

Question

我编写了以下 C++ 代码来有效地分解非常大的数字(数字最大为 24997300729)。 我有一个包含大约 41000 个素数的 vector (我知道拥有这么大的 vector 不是一个好主意，但我想不出解决这个问题的方法)。 此代码立即生成中等大数的质因数分解，但当涉及到诸如 24997300572 之类的数字时，程序停止。

下面是带有一些输出截图的程序:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>

using namespace std;

vector<int> primes = {paste from  

   https://drive.google.com/file/d/1nGvtMMQSa9YIDkMW2jgEbJk67P7p54ft/view?usp=sharing
};

void factorize(int n) {
    if (n == 1)
        return;
    if (find(primes.begin(), primes.end(), n) != primes.end()) {
        cout << n <<" ";            //if n is prime dont'proceed further
        return;
    }

    //obtaining an iterator to the location of prime equal to or just greater than sqrt(n)
    auto s = sqrt(n);
    vector<int>::iterator it = lower_bound(primes.begin(), primes.end(), s);

    if (it == primes.end()) {
        return;                 // if no primes found then the factors are beyond range
    }
    for (auto i = it;i != primes.begin();i--) {
        if (n % *i == 0)
        {
            cout << *i << " ";
            n = n / (*i);
            factorize(n);
            return;             // the two consecutive for() loops should never run one after another
        }

    }
    for (auto i = it;i != primes.end();i++) {
        if (n % *i == 0)
        {
            cout << *i << " ";
            n = n / (*i);
            factorize(n);
            return;         // the two consecutive for() loops should never run one after another
        }
    }
}

int main() {
    unsigned int n;
    cout << "Enter a number between 1 and 24997300729 ";
    cin >> n;
    if (n > 24997300729) {
        cout << "Number out of range;";
        exit(-1);
    }
    factorize(n);
    return 0;
}

没关系

但这不是!!!

我尝试在任何可能的地方使用 long long int 和 long double 来解决大数问题，但这并没有太大帮助。

任何帮助将不胜感激

Answer 1

有点不清楚(至少对我而言)您为何按照您的方式构建程序。

您可以通过仅查找小于或等于该数平方根的质因数来完全分解该数。任何大于那些对的素因数小于一个素因数，因此您只需搜索这些素数即可找到所有素数。任何剩余的因素都可以通过简单的除法而不是搜索来获得。

我可能会即时生成素数的基数(很可能使用筛子)。 24'997'300'729 的平方根是(大约)158'105。快速测试表明，即使没有任何优化工作，Eratosthenes 筛也能在大约 12 毫秒内找到达到该限制的素数。

就我个人而言，除了对我们正在处理的数字大小的限制外，我宁愿对用户可以分解的最大数字没有固定限制，所以如果用户输入接近限制的内容对于 64 位数字，我们找到所有适合 32 位的素数，然后使用它们对数字进行因式分解。这显然会比我们找不到尽可能多的素数要慢，但用户可能不会对因式分解较大数比因式分解较小数花费更长的时间感到惊讶。

因此，实现它，我们可能会得到如下代码:

#include <iostream>
#include <locale>
#include <vector>
#include <string>

using Number = unsigned long long;

auto build_base(Number limit) {
    std::vector<bool> sieve(limit / 2, true);

    for (Number i = 3; i < limit; i += 2) {
        if (sieve[i / 2]) {
            for (Number temp = i * i; temp < limit; temp += i)
                if (temp & 1)
                    sieve[temp / 2] = false;
        }
    }
    return sieve;
}

void factor(Number input, std::vector<bool> const &candidates)
{
    while (input % 2 == 0) {
        std::cout << 2 << "\t";
        input /= 2;
    }

    for (Number i = 1; i < candidates.size(); i++) {
        if (candidates[i]) {
            auto candidate = i * 2 + 1;
            while ((input % candidate) == 0) {
                    std::cout << candidate << "\t";
                    input /= candidate;
            }
        }
    }
    if (input != 1)
        std::cout << input;
}

int main(int argc, char **argv) {
    std::cout.imbue(std::locale(""));

    if (argc != 2) {
        std::cerr << "Usage: factor <number>\n";
        return EXIT_FAILURE;
    }

    auto number = std::stoull(argv[1]);
    auto limit = std::sqrt(number) + 1;
    auto candidates = build_base(limit);

    factor(number, candidates);
}

在高层次上，代码是这样工作的:我们首先找到用户输入数字的平方根之前的素数。由于我们希望所有素数都达到一个极限，因此我们使用埃拉托色尼筛法来找到它们。这构建了一个 bool vector ，其中如果 n 是质数，则 vector[n] 将为真，如果 n 为复合，则为假。它从 3 开始执行此操作(2 是我们现在忽略的一种特殊情况)并划掉三的倍数。然后它找到下一个没有被划掉的数字(在本例中为 5)，并划掉它的倍数。它会继续这样做，直到它到达数组的末尾。为了节省一些空间，它将所有偶数都留在数组之外，因为(除了 2 的特殊情况)我们已经知道它们都不是质数。

一旦我们有了它，我们就可以使用这些质数来找到我们想要分解的数的质因数。这过程非常简单:遍历素数 vector ，并测试每个素数是否均分为目标数。如果是，则打印出来，除以目标数，然后继续。

至少对我来说，这似乎工作得相当可靠，而且相当快。如果我们想更好地分解更大的数字，下一步就是改用分段筛。这可以大大提高作业第一部分的速度，使我们(例如)能够在不超过 10 秒的时间内分解出适合 64 位数字的任何因素。