算法分析

暴力$O(NlogN)$
从1~N枚举每个数用试除法对每个数进行分解质因数，最后把质因数累加即可。
优化$O(N)$
先枚举出1~N的所有质数，大概有$N/lnN个，然后考虑N！中有多个质因子p. 1~n中p的倍数显然有N/p个，P^2的倍数有N/p^2.... P^k的倍数有N/p^k个，然后累加即可。 最终p个个数就是N/p + N/p^2 + … + N/p^k 对于每个p最坏的情况下 所用时间$logN$
那么总的时间N/lnN * logN 近似为 O(N)的