c++ - 计算数字的质数除数(不相异)的总和的有效替代方法，直到 num

Question

据说一个数字有n素因数是否可以计入 n质数(不一定不同)。
例如:

12 = 2*2*3 ---> 12 has 3 prime divisors  

给定数字 a和 b我们必须找到 a! 的此类质数因子的数量/b! (a>=b)。因此，我决定采用以下方式:

long long pre[5000001];

long long solve(int num)
{
    if(!num)
        return 0;
    if(pre[num] || num==1)
        return pre[num];
    int num1=num;
    if(num1%2==0)
    {
        int cnt=0;
        while(num1%2==0)
        {
            num1/=2;
            cnt++;
        }
        pre[num] = solve(num-1) + (solve(num1)-solve(num1-1)) + cnt;
        return pre[num];
    }

    for(int i=3;i<=(int)(sqrt(num1))+1;++i)
    {
        if(num1%i==0)
        {
            int cnt=0;
            while(num1%i==0)
            {
                cnt++;
                num1/=i;
            }
            pre[num] = solve(num-1) + (solve(num1)-solve(num1-1)) + cnt;
            return pre[num];
        }
    }
    if(num>1)
    {
        pre[num]=1 + solve(num-1);
        return pre[num];
    }
}

int main()
{
    int t;
    cin>>t;
    pre[1]=0;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        long long ans = solve(a)-solve(b);
        cout<<ans<<endl;
    }
    return 0;
}

我的方法基本上是计算质数因子的数量并存储它们，因为 a 的极限和 b是<=5000000 . pre[num]给出所有数的质因数之和 <=num .但它会导致较大输入的运行时错误，例如 a=5000000 b=4999995 .有没有更好的方法来做到这一点，或者可以调整当前的方法以获得更好的解决方案？

Answer 1

您达到了递归的限制。

要解决您的问题，您可以首先构建从 0 到 a 的数组:

int main()
{
    int max_a = 0;
    int t;
    cin >> t;
    pre[1] = 0;
    while(t--)
    {
        int a, b;
        cin >> a >> b;

        for (int i = max_a; i < a; ++i) {
            solve(i); // memoization until `a` max recursion is limited to 1 :)
        }
        max_a = std::max(max_a, a);
        long long ans = solve(a) - solve(b);
        std::cout << ans << std::endl;
    }
}