J.Doe - 1 year ago 108
C++ Question

Fastest way to find dividers of a number in C++

I am trying to do an exercise in which you should find number of dividers of factorial of nth number:

https://www.e-olymp.com/en/problems/124

So here is my code:

``````int fact(int n){
return (n==1 || n==0) ? 1 : n*fact(n-1);
}
long long int a,b=1,c=0;
cin>>a;
long long int y=fact(a);
while(b!=y){
if(y%b==0){
c++;
}
b++;
}
cout<<c+1<<endl;
``````

But this code takes too much time and I need something quicker. Don't give code, algorithm will be enough.

In this task `1 <= N <= 45`. Obviously, `N` is too large to calculate it directly.

You should implement another approach. Just iterate from the `1` to `N` and do the prime factorization for every `i, 1 < i <= N`. Then you can easily find the prime factorization of `N!`, just merge factorization of every `i, 1 < i <= N`. After that calculate the total number of divisors using previously calculated factorization.

Example for 6!:

``````2 = 2
3 = 3
4 = 2 ^ 2
5 = 5
6 = 3 * 2
``````

So:

``````6! = 2 ^ 4 * 3 ^ 2 * 5
``````

And the number of divisors:

``````(4 + 1) * (2 + 1) * (1 + 1) = 30
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download