J.Doe - 8 days ago 4x

C++ Question

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
```

Source (Stackoverflow)

Comments