给定一个数字1 <= n <= 10^18，我怎样才能以最小的时间复杂度分解它？

互联网上有很多帖子讨论如何找到主要因素，但没有一个（至少从我所看到的）说明它们的好处，比如在特定情况下。

除了埃拉托色尼筛法之外，我还使用 Pollard 的 rho 算法：

• Using sieve, find all prime numbers in the first 10⁷ numbers, and then divide n with these primes as much as possible.
• 现在使用 Pollard 的 rho 算法尝试找到其余的素数，直到 n 等于 1。

我的实施：

#include <iostream>
#include <vector>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>

using namespace std;

typedef unsigned long long ull;
typedef long double ld;
typedef pair <ull, int> pui;
#define x first
#define y second
#define mp make_pair

bool prime[10000005];
vector <ull> p;

void initprime(){
    prime[2] = 1;
    for(int i = 3 ; i < 10000005 ; i += 2){
        prime[i] = 1;
    }
    for(int i = 3 ; i * i < 10000005 ; i += 2){
        if(prime[i]){
            for(int j = i * i ; j < 10000005 ; j += 2 * i){
                prime[j] = 0;
            }
        }
    }
    for(int i = 0 ; i < 10000005 ; ++i){
        if(prime[i]){
            p.push_back((ull)i);
        }
    }
}

ull modularpow(ull base, ull exp, ull mod){
    ull ret = 1;
    while(exp){
        if(exp & 1){
            ret = (ret * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return ret;
}

ull gcd(ull x, ull y){
    while(y){
        ull temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

ull pollardrho(ull n){
    srand(time(NULL));
    if(n == 1)
        return n;
    ull x = (rand() % (n - 2)) + 2;
    ull y = x;
    ull c = (rand() % (n - 1)) + 1;
    ull d = 1;
    while(d == 1){
        x = (modularpow(x, 2, n) + c + n) % n;
        y = (modularpow(y, 2, n) + c + n) % n;
        y = (modularpow(y, 2, n) + c + n) % n;
        d = gcd(abs(x - y), n);
        if(d == n){
            return pollardrho(n);
        }
    }
    return d;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
initprime();
ull n;
cin >> n;
ull c = n;
vector <pui> o;
for(vector <ull>::iterator i = p.begin() ; i != p.end() ; ++i){
    ull t = *i;
    if(!(n % t)){
        o.push_back(mp(t, 0));
    }
    while(!(n % t)){
        n /= t;
        o[o.size() - 1].y++;
    }
}
while(n > 1){
    ull u = pollardrho(n);
    o.push_back(mp(u, 0));
    while(!(n % u)){
        n /= u;
        o[o.size() - 1].y++;
    }
    if(n < 10000005){
        if(prime[n]){
            o.push_back(mp(n, 1));
        }
    }
}
return 0;
}

有没有更快的方法来分解这些数字？如果可以的话，请解释原因并附上源代码。

Approach

Lets say you have a number n that goes up to 10¹⁸ and you want to prime factorise it. Since this number can be as small as unity and as big as 10¹⁸, all along it can be prime as well as composite, this would be my approach -

1. Using 米勒·拉宾素性测试，确保该数字是合数。
2. Factorise n using primes up to 10⁶, which can be calculated using sieve of Eratosthenes.

Now the updated value of n is such that it has prime factors only above 10⁶ and since the value of n can still be as big as 10¹⁸, we conclude that the number is either prime or it has exactly two prime factors (not necessarily distinct).

1. 再次运行 Miller Rabin 以确保该数字不是质数。
2. Use Pollard rho 算法得到一个素因数。

现在你已经完成了因式分解。

让我们看看上述方法的时间复杂度：

• 米勒·拉宾接受O(log n)
• 埃拉托斯特尼筛法O(n*log n)
• 我分享的 Pollard rho 的实现需要O(n^0.25)

时间复杂度

步骤 2 花费的最大时间等于O(10^7)，这又是上述算法的复杂度。这意味着您可以在一秒钟内找到几乎所有编程语言的因式分解。

空间复杂度

空间仅在实施筛子的步骤 2 中使用，并且等于O(10^6)。再次强调，非常实用。

执行

完整代码实施于C++14。该代码有一个隐藏的错误。您可以在下一部分中揭示它，也可以跳到挑战；）

代码中的错误

In line 105，迭代直到i<=np。否则，您可能会错过以下情况prime[np]=999983是一个素因数

挑战

给我一个值n，如果有的话，其中共享代码导致错误的素因数分解。

Bonus

有多少个这样的值n exist ?

对于这样的 n 值，断言Line 119可能会失败。

我们打电话吧P=999983。表格中的所有数字n = p*q*r其中 p、q、r 是素数 >=P使得其中至少一个等于P将导致错误的质因数分解。

There are exactly four such numbers: {P₀³, P₀²P₁, P₀²P₂, P₀P₁²}, where P₀ = P = 999983, P₁ = next_prime(P₀) = 1000003, P₂ = next_prime(P₁) = 1000033.