针对大数的高效Prime分解

Question

我一直在研究一个小问题,我需要将18位数字计算到它们各自的素数分解中.考虑到它确实有效,所有的东西都会编译并运行得很好,但我希望减少素数分解的运行时间.我已经实现了递归和线程,但我想我可能需要一些帮助来理解大数计算的可能算法.

每次我在预制的4个数字上运行时,大约需要10秒钟.如果有任何想法,我想减少到0.06秒.

我注意到了一些像Eratosthenes筛选的算法,并在计算之前生成了所有素数的列表.我只是想知道是否有人可以详细说明.例如,我在理解如何将Eratosthenes的Sieve实现到我的程序中或者它是否是一个好主意时遇到了问题.关于如何更好地接近这一点的任何和所有指针都会非常有用!

这是我的代码:

#include <iostream>
#include <thread>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

vector<thread> threads;
vector<long long> inputVector;
bool developer = false; 
vector<unsigned long long> factor_base;
vector<long long> primeVector;

class PrimeNumber
{
    long long initValue;        // the number being prime factored
    vector<long long> factors;  // all of the factor values
public:
    void setInitValue(long long n)
    {
        initValue = n;
    }
    void addToVector(long long m)
    {
        factors.push_back(m);
    }
    void setVector(vector<long long> m)
    {
        factors = m;
    }
    long long getInitValue()
    {
        return initValue;
    }
    vector<long long> getVector()
    {
        return factors;
    }
};

vector<PrimeNumber> primes;

// find primes recursively and have them returned in vectors
vector<long long> getPrimes(long long n, vector<long long> vec)
{
    double sqrt_of_n = sqrt(n);

    for (int i = 2; i <= sqrt_of_n; i++)
    {
        if (n % i == 0) 
        {
            return vec.push_back(i), getPrimes(n / i, vec); //cause recursion
        }
    }

    // pick up the last prime factorization number
    vec.push_back(n);

    //return the finished vector
    return vec;
}

void getUserInput()
{
    long long input = -1;
    cout << "Enter all of the numbers to find their prime factors. Enter 0 to compute" << endl;
    do
    {
        cin >> input;
        if (input == 0)
        {
            break;
        }
        inputVector.push_back(input);
    } while (input != 0);
}

int main() 
{

    vector<long long> temp1;   // empty vector
    vector<long long> result1; // temp vector

    if (developer == false)
    {
        getUserInput();
    }
    else
    {
        cout << "developer mode active" << endl;
        long long a1 = 771895004973090566;
        long long b1 = 788380500764597944;
        long long a2 = 100020000004324000;
        long long b2 = 200023423420000000;
        inputVector.push_back(a1);
        inputVector.push_back(b2);
        inputVector.push_back(b1);
        inputVector.push_back(a2);
    }

    high_resolution_clock::time_point time1 = high_resolution_clock::now();

    // give each thread a number to comput within the recursive function
    for (int i = 0; i < inputVector.size(); i++)
    {   
        PrimeNumber prime;
        prime.setInitValue(inputVector.at(i));
        threads.push_back(thread([&]{
            prime.setVector(result1 = getPrimes(inputVector.at(i), temp1));
            primes.push_back(prime);
        }));
    }

    // allow all of the threads to join back together.
    for (auto& th : threads)
    {
        cout << th.get_id() << endl;
        th.join();
    }

    high_resolution_clock::time_point time2 = high_resolution_clock::now();

    // print all of the information
    for (int i = 0; i < primes.size(); i++)
    {
        vector<long long> temp = primes.at(i).getVector();

        for (int m = 0; m < temp.size(); m++)
        {
            cout << temp.at(m) << " ";
        }
        cout << endl;
    }

    cout << endl;

    // so the running time
    auto duration = duration_cast<microseconds>(time2 - time1).count();

    cout << "Duration: " << (duration / 1000000.0) << endl;

    return 0;
}

Answer 1

试验分割仅适用于小数字因子.对于n最多2 ^ 64,你需要一个更好的算法:我建议从车轮分解开始得到小因子,然后用Pollard的rho算法来得到其余的.如果试验除法为O(sqrt(n)),则rho为O(sqrt(sqrt(n))),因此速度更快.对于2 ^ 64,sqrt(n)= 2 ^ 32,但sqrt(sqrt(n))= 2 ^ 16,这是一个巨大的改进.您应该期望在最多几毫秒内计算您的数字.

我没有用于分解的C++代码,但我确实有可读的Python代码.如果您要我发布,请告诉我.如果你想更多地了解车轮分解和rho算法,我的博客上有很多素数.

Answer 2

通过更改循环可以轻松实现两倍的简单加速：

if (n % 2) {
    return vec.push_back(i), getPrimes(n / i, vec);
}

for (int i = 3; i <= sqrt_of_n; i += 2)
{
    if (n % i == 0) 
    {
        return vec.push_back(i), getPrimes(n / i, vec); //cause recursion
    }
}

您首先应该测试该数字为 2。然后，从 3 开始再次测试，一次将循环增加 2。您已经知道 4、6、8... 是偶数，并且有 2 作为因数。针对偶数进行测试可以将复杂性降低一半。

要因式分解一个数字，N您只需要质数 <= sqrt(N)。对于 18 位数字，您只需测试所有小于 的素数1e9，并且由于小于9800 万个素数2e9，您可以轻松地在当今的计算机上存储 1 亿个数字并并行运行因式分解。如果每个数字占用 8 字节 RAM ( int64_t)，则 1 亿个素数将占用 800 MB 内存。该算法是SPOJ 问题#2（素数生成器）的经典解决方案。

列出所有适合 32 位整数的小素数的最佳方法是构建埃拉托斯特尼筛法。我告诉过您，我们需要小于 sqrt(N) 的素数来分解任何 N，因此要分解 64 位整数，您需要适合 32 位数字的所有素数。