6.简单组合数学&简单数论
6.1 分解质因数/判断素数/求因子和/求因子数量
对于任意的正整数而言，其因子一定是两两成对的：若p是x的因子，x/p也一定是x的因子。
所以以上的问题有个共同的解法：O(√x)遍历所有不大于√x的的因子即可。
要注意x的完全平方数的特判。
下面给出求因子和的关键代码：
| int i,sum=0; for(i=1;i*i<x;i++){ if(x%i==0)sum+=i+x/i; //既计算了因子i，也计算了因子x/i } if(i*i==x)sum+=i; //特判完全平方数 |
6.2 欧拉筛
如何快速得到1到n的所有素数？
可以这样快速筛出来：先将所有2的倍数标记为合数，然后把所有3的倍数标记为合数，然后遇到4，刚刚在2的时候就被标记了，跳过；接下来把所有5的倍数标记为合数……
最终所有没被标记的就是素数了。复杂度为O(nlogn)。
还有一种更优秀的筛法：
对于每个数x，对所
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
算法笔面试宝典 文章被收录于专栏
算法笔面试真题解析
