[关闭]
@Bei-S 2019-02-26T12:21:25.000000Z 字数 386 阅读 336

数论进阶指南

数论



线性筛

复杂度:

A. 线性筛素数

自己对线性筛素数这东西其实一直很困惑,毕竟不理解为什么加了

  1. if(i%pri[j]==0) break;

这一句之后,就可以保证每个数只被最小质因子筛去了。今天就开始补坑!

证明:一个数i当它找到它的最小质因子pri[j]时(因为pri数组中质数从小到大),分为两种情况:

a. i为合数,我们不妨设,
如果继续筛的话,我们其实是把筛去,
那么可以写作
此时N应当在时被筛去,才满足被最小质因子筛去。
同理对于

b. i为质数,此时我们一定是遍历到i本身,即,我们之后就没有素数了,即可

线性筛素数

B.线性筛欧拉函数

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注