The-Legend's blog

Number of divisors of factorial

By The-Legend, history, 8 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?
»
8 years ago, # |
  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
»
8 years ago, # |
  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
»
8 years ago, # |
← 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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 6   Vote: I like it -14 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← 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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

          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

          → Reply
»
8 years ago, # |
← Rev. 6   Vote: I like it -33 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← 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
»
8 years ago, # |
← 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
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Maybe can help.

→ Reply