题解 P2043【质因数分解】

critnos · 2020-05-08 10:21:12 · 题解

正解是 O(n) 的。

如何快速求出 n! 内有多少个质因数 p？

一个 \log n 的算法：ans=\lfloor\dfrac n p\rfloor+\lfloor\dfrac n {p^2}\rfloor+\lfloor\dfrac n {p^3}\rfloor\dots

s=0;
for(j=n/p;j;j/=p)
    s+=j;

欧拉筛出 n 以内的素数是 O(n) 的。

对每个素数都求一下，这道题就做完了。

根据素数个数公式，当 n 趋向于 \inf 时 \pi(n)（n 以内的素数个数）等于 \dfrac n {\log n}，每个素数计算的复杂度为 \log n，所以 \dfrac n {\log n} \times \log n=n，故而时间复杂度为 O(n)，证毕。