### The-Legend's blog

By The-Legend, history, 5 years ago, Hello!

What is the fastest way to calc the number of divisors of n! , s.t 1 <= n <= 1e8.

Number of test cases <= 5000 .

I've stucked at this point while solving this problem EasyFact Comments (14)
 » Auto comment: topic has been updated by The-Legend (previous revision, new revision, compare).
 » Auto comment: topic has been updated by The-Legend (previous revision, new revision, compare).
 » 5 years ago, # | ← Rev. 2 →   What's wrong with prime factorization? Since the number of test cases <= 5000, you should pre-calculate the prime factorization of all numbers <= 10^8. Now use this to answer each test case in sqrt(n) * log(n).
•  » » 5 years ago, # ^ | ← Rev. 6 →   .
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Prime divisors of N! (N factorial) are less or equal to N. So, for each prime P ( <= N), you can calculate its power in factorization of N! using this code: int calc(int n, int p) { // finds maximum alpha such that n mod p^alpha = 0 int alpha = 0; while (n) { n /= p; alpha += n; } return alpha; } 
•  » » » » There are 5 millions primes up to 1e8, for each one of them I need to calling " calc " , and this is for one test case , it's too slow.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   You only need to check primes upto since the power of all primes greater than in n! will be 1. And you can precalculate how many primes are in the range •  » » » » » » Yeah got it. How to solve for higher n?
•  » » » » » » I don't. I'm genuinely interested — how do you precalculate how many primes are in the range [sqrt(n), n]
 » 5 years ago, # | ← Rev. 6 →   UPD:I've misunderstood the problem.Ignore this comment,thanks.
•  » » 5 years ago, # ^ | ← Rev. 2 →   You are wrong.I want N! not NTry this caseT = 1;N = 5;then N! = 120 = 2^3 * 3 * 5 then the number of divisors equal to 16Your answer is 2
 » 5 years ago, # | ← Rev. 7 →   We need to find for all primes in range [1, N] powers in which that numbers occurs in the N!'s factorization. For primes from its clear. For any prime (lets call that set "big primes") we can observe, that d's power in factorizations of numbers from [1, N] is only 0 or 1. Thus d's power in the answer equal to amount of numbers in [1, N] which d devides. Lets call that power p(d). Then we can observe that all numbers with same value of p(·) is a consecutive segment of "big primes" and moreover p(·) has only values.Amount of big primes with fixed p(d) (= amount of primes with exactly p(d) multiples) equals . Any of them gives p(d) + 1 to the answer thus in the result we need to assign ans = ans * (p(d) + 1)C.Im sure that my explanation was really ugly and I hope code will be useful.
•  » » 5 years ago, # ^ | ← Rev. 2 →   Thanks :)
 » Maybe can help.