时间戳

首页 > 解决方案 > 有没有办法在c ++中分解大数

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

问题描述

我编写了以下 C++ 代码来有效地分解非常大的数字（数字高达 24997300729）。我有一个包含大约 41000 个素数的向量（我知道拥有这么大的向量不是一个好主意，但无法解决这个问题）。此代码立即生成中等大数的素数分解，但是当涉及到诸如 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尽可能解决大量问题，但这并没有太大帮助。

任何帮助将不胜感激

标签： c++

解决方案

有点不清楚（至少对我来说）究竟为什么你以你的方式构建程序。

您可以通过仅查找小于或等于该数字平方根的素因子来完全分解一个数字。任何比那些比那些小的素因数大的素因数，所以你只需要搜索那些就可以找到所有的素因数。剩下的任何因素都可以通过简单的除法得到，而不是搜索。

我可能会即时生成素数的基数（很可能使用筛子）。24'997'300'729 的平方根是（大约）158'105。一项快速测试表明，即使没有任何优化工作，埃拉托色尼的筛子也会在大约 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);
}

在高层次上，代码的工作原理是这样的：我们首先找到直到用户输入的数字的平方根的素数。由于我们希望所有素数都达到极限，因此我们使用 Eratosthenes 筛子来找到它们。这构建了一个布尔向量，vector[n]如果是素数，则为真，如果是合n数，则为假n。它从 3 开始执行此操作（2 是我们暂时忽略的特殊情况）并划掉 3 的倍数。然后它找到下一个没有被划掉的数字（在这种情况下是五个），并划掉它的倍数。它继续这样做，直到到达数组的末尾。为了节省一些空间，它将所有偶数排除在数组之外，因为（除了 2 的特殊情况）我们已经知道它们都不是素数。

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

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

推荐阅读