2

A number is said to have n prime divisors if it can factored into n prime numbers (not necessarily distinct).
E.g.:

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

Given numbers a and b we have to find the number of such prime divisors of a!/b!(a>=b). Hence I decided to do the following way:

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;
}

My approach was to basically to calculate the number of prime divisors and store them because the limit for a and b was <=5000000. pre[num] gives the sum of number of prime divisors of all numbers <=num. But it results in run-time error for larger inputs such as a=5000000 b=4999995. Is there any better way to do this or the present approach can be tweaked for a better solution?

1
  • 1
    @Jarod42....no since I mentioned pre[num] gives the sum of number of prime divisors till num. You can tell ans = f(b+1)...+f(a) where f(num) gives number of prime divisors of num.
    – yobro97
    Mar 30, 2017 at 21:58

1 Answer 1

1

You reach your limit of recursion.

To fix your problem, your may build your array from 0 to a first:

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;
    }
}
3
  • I initially thought this was the case, however I thought c++ didn't have a recursion limit. See Does C++ limit recursion depth?. Mar 30, 2017 at 23:25
  • You were correct @Jarod42 . But this time my solution was judged time limit exceeded although the run-time error message was gone. Any better way to solve this problem?
    – yobro97
    Mar 31, 2017 at 4:58
  • Your array can be constexpr on the principle.You may so generate the array once in other file, and hardcode it directly in main. (I failed to construct that array as consexpr with "constexpr evaluation hit maximum step limit; possible infinite loop?" :( )
    – Jarod42
    Mar 31, 2017 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.