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

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3627 |

4 | ksun48 | 3547 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3463 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3303 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 209 |

2 | Um_nik | 196 |

3 | YouKn0wWho | 192 |

4 | Errichto | 182 |

5 | sus | 181 |

5 | awoo | 181 |

7 | tourist | 175 |

8 | SecondThread | 172 |

9 | -is-this-fft- | 171 |

10 | Radewoosh | 170 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2021 16:37:23 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

.

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:

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.

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 rangeYeah 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]

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

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

We need to find for all primes in range [1,

N] powers in which that numbers occurs in theN!'s factorization. For primes from it`s clear. For any prime (lets call that set "big primes") we can observe, thatd's power in factorizations of numbers from [1,N] is only 0 or 1. Thusd's power in the answer equal to amount of numbers in [1,N] whichddevides. Lets call that powerp(d). Then we can observe that all numbers with same value ofp(·) is a consecutive segment of "big primes" and moreoverp(·) has only values.Amount of big primes with fixed

p(d) (= amount of primes with exactlyp(d) multiples) equals . Any of them givesp(d) + 1 to the answer thus in the result we need to assignans=ans* (p(d) + 1)^{C}.I`m sure that my explanation was really ugly and I hope code will be useful.

Thanks :)

Maybe can help.