数学知识（一）学习笔记

 第一种O（n）从2到n-1遍历着去除

优化：利用sqrt；

由于sqrt比较慢，继续考虑i*i

而i*i<n判断存在溢出风险

所以用i<=n/i,推荐做法！！

由于从小到大枚举，因此i一定是质因数，不会是合数 

而且必须是它本身！！ 

筛法求质数

没有优化的是把所有的数的倍数统统删掉

依次把2的所有倍数，3的所有倍数，依次删除 ，用之前还没有被删掉的数字去筛选后面的，保证了2~p-1都没有p的因数

 时间复杂度判定（未优化版本）

nlogn 欧拉常数c 无限不循环小数

优化后复杂度分析如下

 

 

除了埃氏筛法，我们还有线性筛法 

他只是埃氏筛法的一个优化，防止一个数被筛掉几次，去掉了一些O（1）的操作

 辗转相除法

 

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120769683