The-Legend's blog

Number of divisors of factorial

By The-Legend, history, 10 years ago, In English

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

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by The-Legend (previous revision, new revision, compare).

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by The-Legend (previous revision, new revision, compare).

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +25 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 6  
    Vote: I like it -14 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      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;
}
      → Reply
»
10 years ago, hide # |
← Rev. 6  
Vote: I like it -33 Vote: I do not like it

UPD:I've misunderstood the problem.Ignore this comment,thanks.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    You are wrong.

    I want N! not N

    Try this case

    T = 1;

    N = 5;

    then N! = 120 = 2^3 * 3 * 5 then the number of divisors equal to 16

    Your answer is 2

    → Reply
»
10 years ago, hide # |
← Rev. 7  
Vote: I like it +29 Vote: I do not like it

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 it`s 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.

I`m sure that my explanation was really ugly and I hope code will be useful.

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Maybe can help.

→ Reply