六、简单组合数学&简单数论
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，对所有小于x的素数p而言，将x*p筛掉。遇到x%p===0则直接跳出。可以证明，每个合数一定会被这种筛法筛一
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
技术岗必备：笔面试算法 文章被收录于专栏
<p> 本专刊由牛客官方团队打造 </p> <p> 算法作为技术岗位必会的内容，在笔面试中的重要性越来越高，但有很多同学对于算法怎么学习，怎么刷题以及如何自己调试依然一无所知<span></span> </p> <p> 牛客官方团队打造了本书内容帮助大家了解校招算法套路增强通过概率，为校招保驾护航 </p>
查看16道真题和解析
格力公司福利 425人发布
