在 C++ 中有效地计算 O(n^(1/3)) 中数字的除数

Question

我在这里找到了一种有效的算法来计算 O(n^(1/3)) 中数字的除数：https://codeforces.com/blog/entry/22317

我已经在下面的代码中实现了算法。但它不能正常工作。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define endl "\n"
#define pi 2*acos(0)

#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define mem(a, val) memset(a, val, sizeof a)

vector<int> prime(10000000, 1); // array size is 10^7
void sieve(ll n){
    prime[0]=prime[1]=0;
    for(ll i=2; i<=sqrt(n); i++){
        if(prime[i]==1){
            for(ll j=2; i*j<=n; j++) prime[i*j]=0;
        }
    }
}
bool isPrime(ll n){
    if(n<2) return false;
    return prime[n];
}

vector<int> primeTable;
ll numberOfDivisors(ll n){
    for(int i=0; i<1000000; i++){
        if(prime[i]==1) primeTable.pb(i);
    }
    ll ans=1;
    for(int i=0; ; i++){
        if(primeTable[i]*primeTable[i]*primeTable[i]>n) break;
        ll cnt=1;
        while(n%primeTable[i]==0){
            n=n/primeTable[i];
            cnt++;
        }
        ans*=cnt;
    }
    double sqn=sqrt(n);
    if(isPrime(n)) ans*=2;
    else if((sqn-floor(sqn))==0 and isPrime((ll)sqn)) ans*=3;
    else if(n!=1) ans*=4;

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll n;
    cin >> n;
    ll N=cbrt(n);
    sieve(N);
    cout << numberOfDivisors(n) << endl;

    return 0;
}

即对于15它returns 2（应该是4），对于100它returns 6（应该是9），对于999它returns 8（这是正确的），但对于 9999，它又是 returns 6（应该是 12）。我认为第 42 行和第 45 行之间有问题。但我找不到错误。请帮我找出错误。

Answer 1

你在vector<int> prime(10000000, 1)这里设置prime的初始值为1。然后在 seive(ll n) 函数中将 prime 的值更新为 n。因此 n+1 到 10000000 prime 的值将保持为 1。在您的主要功能中，您运行 sieve(N) 为 ll N=cbrt(n)。因此，您的 isPrime(n) 不正确，因为 n 可能大于 N=cbrt(n)。修复你的代码是好的。

从博客post了解到，这个算法是为了求长整型的因数。他们还提到要检查素数使用 Miller Rabin。您检查 isPrime(n) 的方式不适用于大整数。

同时更新这部分（将1000000更改为cbrt(n)）：

ll numberOfDivisors(ll n){
    for(int i=0; i<1000000; i++){
        if(prime[i]==1) primeTable.pb(i);
    }

在 C++ 中有效地计算 O(n^(1/3)) 中数字的除数

Efficiently Counting Divisors of a Number in O(n^(1/3)) in c++

c++

algorithm

debugging

coding-efficiency