如何加速这个素数测试

Question

我希望找到给定数字的最大质因数。经过几次尝试，我已经改进了测试以处理相当大的数字（即在毫秒内达到十亿级别）。问题是，如果超过十亿，执行时间会变得无限长。我想知道是否可以进行更多的改进并减少执行时间。我希望有更好的执行时间，因为在此链接Prime Factors Calculator中，执行时间非常快。目标数字是600851475143。代码相当自说明。注意：我考虑使用埃拉托色尼筛法算法，但对于执行时间没有什么帮助。

#include <iostream>
#include <cmath>

bool isPrime(int n)
{
    if (n==2)
        return true;

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

    for (int i(3);i<=sqrt(n);i+=2) // ignore even numbers and go up to sqrt(n)
        if (n%i==0)
            return false;

    return true;
}

int main()
{
    int max(0);
    long long target(600851475143);

    if( target%2 == 0 )
        max = 2;

    for ( int i(3); i<target; i+=2 ){ // loop through odd numbers. 
        if( target%i == 0 )  // check for common factor
            if( isPrime(i) ) // check for prime common factor
                max = i;
    }

    std::cout << "The greatest prime common factor is " << max << "\n";


    return 0;
}

- CroCo

---

尝试使用更高级的算法，例如Miller-Rabin素性测试。 - rlee827

附注：sqrt是一个浮点函数；您依赖它返回一个精确的结果，但不能保证它会这样做。 - user1084944

@Hurkyl 无论如何，他都应该测试 i * i <= n 并避免使用 sqrt 调用。 - Alnitak

@Alnitak i <= n / i 避免了整数溢出的问题。 - Will Ness

这个问题在 Stack Overflow 上已经被问了 285 次了，顺便说一句。 :) - Will Ness

Answer 1

我能看到一个明显的优化：

for (int i(3);i<=sqrt(n);i+=2) // ignore even numbers and go up to sqrt(n)

可以将sqrt的结果缓存到一个变量中，而不是每次都重新计算。

auto maxFactor = static_cast<int>sqrt(n);
for (int i(3); i <= maxFactor; i+=2);

我相信这个方法能够加速的原因是sqrt涉及到浮点算术，编译器通常不会在优化浮点算术方面慷慨。gcc有一个特殊的标志ffast-math来明确启用浮点数优化。

对于你提到的目标范围内的数字，您需要更好的算法。重复除法就足够了。

这是代码(http://ideone.com/RoAmHd)，它几乎不需要任何时间来完成。

int main() {
    long long input = 600851475143;
    long long mx = 0;
    for (int x = 2; x <= input/x; ++x){
        while(input%x==0) {input/=x; mx = x; }

    }
    if (input > 1){
        mx = input;
    }
    cout << mx << endl;
    return 0;
}

重复除法的思想是：如果一个数已经是因子 p 的倍数，那么它也是 p^2, p^3, p^4.... 的倍数。因此，我们不断消除因子，只留下最终可被质因数整除的因子。

- bashrc

---

应该这样写：auto maxFactor = static_cast<long>(sqrt(n)); 这样，你就不会在每次比较时将 i 提升为 float。还有一种非常快速的方法可以获得平方根的整数部分，而不使用浮点数。 - Spencer

@Spencer 完全没有必要进行任何平方根运算。 - Alnitak

如果你将2单独处理，然后从x = 3开始循环并以2递增，你可以将循环所需的时间减半。 - rossum

重复除法是这里的关键优化，对于那个数字（当然对于质数来说，sqrt的东西更重要，因为没有可以除掉的除数）。它还消除了素性测试的需要，前提是潜在的除数按升序枚举。 - Will Ness

@rossum，你忘记加上 "然后做 for( x=3; ...; x+=2) ..." 了。 - Will Ness

Answer 2

您不需要质数测试。请尝试使用以下算法：

function factors(n)
    f := 2
    while f * f <= n
        if n % f == 0
            output f
            n := n / f
        else
            f := f + 1
    output n

你不需要进行素数测试，因为试除法的因子在每一步都会增加1，所以任何复合试除因子都已经被其更小的质因子处理过了。

我将让您使用适当的数据类型在C++中实现。这不是分解整数的最快方法，但对于欧拉计划3足够了。

- user448810

Answer 3

请注意，除了2和3之外，所有质数都与6的倍数相邻。

以下代码通过以下方式减少总迭代次数：

• 利用上述提到的事实
• 每次找到新的质因数时减小target

---

#include <iostream>


bool CheckFactor(long long& target,long long factor)
{
    if (target%factor == 0)
    {
        do target /= factor;
        while (target%factor == 0);
        return true;
    }
    return false;
}


long long GetMaxFactor(long long target)
{
    long long maxFactor = 1;

    if (CheckFactor(target,2))
        maxFactor = 2;

    if (CheckFactor(target,3))
        maxFactor = 3;

    // Check only factors that are adjacent to multiples of 6
    for (long long factor = 5, add = 2; factor*factor <= target; factor += add, add = 6-add)
    {
        if (CheckFactor(target,factor))
            maxFactor = factor;
    }

    if (target > 1)
        return target;
    return maxFactor;
}


int main()
{
    long long target = 600851475143;
    std::cout << "The greatest prime factor of " << target << " is " << GetMaxFactor(target) << std::endl;
    return 0;
}

- barak manos

---

对于这个特定的数字，i 的大小并不重要，因为它所能获得的最大值可以适应一个 short。考虑到您似乎已经了解素数测试，我很惊讶您没有完全消除 sqrt 调用。 - Alnitak

@Alnitak：600851475143适合使用short吗？为什么要消除对函数sqrt的调用？ - barak manos

除数适合于短整型，而不是被分解的数字。你应该消除对sqrt函数的调用，因为与比较“i * i”和“n”相比，它非常昂贵。 - Alnitak

@Alnitak：这是一个函数调用与O(n)次乘法的比较。你怎么能确定后者总是更有效率呢？ - barak manos

@Alnitak：无论如何...我已经完全改变了我的答案。由于OP正在执行相同“大小”的两个单独循环来实现完全相同的（最终）目的，因此我决定，我不会尝试改进他/她的解决方案，而是提出一个新的解决方案。 - barak manos

Answer 4

for ( int i(3); i<target; i+=2 ){ // loop through odd numbers. 
    if( target%i == 0 )  // check for common factor
        if( isPrime(i) ) // check for prime common factor
            max = i;

这段代码中，几乎所有时间都花费在前两行，而不是素性检查。你将目标除以从3到target-1的所有数字。这大约需要target/2次除法。

此外，target是long long类型，而i只是int类型。可能会出现大小不足的情况，导致无限循环。

最后，这段代码没有计算最大质因数。它计算了目标的最大质因子，并且效率非常低下。那么你真正需要什么呢？

在C++中，将任何东西称为“max”都是一个坏主意，因为max是一个标准函数。

- user31264

Answer 5

这是我的基本版本：

int main() {
    long long input = 600851475143L;

    long long pMax = 0;

    // Deal with prime 2.
    while (input % 2 == 0) {
        input /= 2;
        pMax = 2;
    }

    // Deal with odd primes.
    for (long long x = 3; x * x <= input; x += 2) {
        while (input % x == 0) { 
            input /= x;
            pMax = x;
        }
    }

    // Check for unfactorised input - must be prime.
    if (input > 1) {
        pMax = input;
    }

    std::cout << "The greatest prime common factor is " << pMax << "\n";

    return 0;
}

通过使用牛顿-拉弗森整数平方根方法来设置（大部分）固定的循环限制，可能可以进一步加快速度。如果可用，这将需要重写主循环。

    long long limit = iSqrt(input)
    for (long long x = 3; x <= limit; x += 2) {
        if (input % x == 0) {
            pMax = x;
            do {
                input /= x;
            } while (input % x == 0);
            limit = iSqrt(input); // Value of input changed so reset limit.
        }
    }

只有在找到新的因数且 input 的值已更改时才会计算平方根。

- rossum