J.Doe J.Doe - 1 month ago 12
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.

Answer

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