SPOJ DIVFACT - Divisors of factorial

vsukeeshbabu · May 30, 2015, 5:10pm

How to do this Question ?

My Code takes 8.22 seconds !

But the time limit is 1 sec .

Thanks in advance !

vippu95 · May 31, 2015, 3:28pm

Use Seive to find all the prime numbers upto 100000.
For each prime p , the power of p in n! is given by :
power(p) = n/p + n/p^2 + n/p^3 …until we get a zero
Our ans is for each prime p :
(power(p1)+1) * (power(p2)+1) * … (power(pk)+1) , assuming there are k prime numbers less than 100000

adi28galaxyak · June 4, 2015, 5:12pm

Can you tell me how did you deduce points 2 and 3.

mani_naik · June 28, 2019, 3:27pm

It’s legendre’s formula

aashishp · January 17, 2022, 7:38am

What is the time complexity of 2nd step?
Is it lesser than finding the prime factorisation of each of the numbers from 1 to N?