数论里面常用的时间复杂度分析：
- 1 + 1/2 + 1/3 + … + 1/n 约等于 logn
- 如果把上面的1和分母为合数的都去掉的话 1/2 + 1/3 + 1/5 + .. + 1/n 约等于 loglogn
- 对于一个n!分解质因数的话，这个1~n中最多有n/logn 个质因数 对于每个质因数p要处理
n/p + n/p^2 + n/p^3 ... //大约logp(n)项 放缩一下为logn项
- 因此总的时间复杂度为 n/logn * logn = 大约为O(n)的，因此阶乘分解是时间复杂度为O(N)的
- n以内的质数个数大约为n/logn 个， 约数个数上限为2sqrt(n)
第二个咋证啊？
请看这里：闫氏证明法
404了？
这是提高课的视频，你没买的话看不到。关于第二项的证明，其实y总没有给出，只是说明埃氏筛法中用到了它，并且直接给出结论就是loglogn。所有y总说这个很常用记住就好~~
哦哦，好的