SPOJ DIVFACT - Divisors of factorial

general
, , , ,
1

How to do this Question ?

DIVFACT

My Code takes 8.22 seconds !

But the time limit is 1 sec .

Thanks in advance ! :slight_smile:

2

  1. Use Seive to find all the prime numbers upto 100000.

  2. For each prime p , the power of p in n! is given by :
    power§ = n/p + n/p^2 + n/p^3 …until we get a zero

  3. 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

Code : http://ideone.com/eyT4zx

2 Likes
3

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