需要注意的是 该筛法对后序积性函数应用十分有用
朴素法
在大于1的[自然数] 中,除了1和它本身以外不再有其他[因数] 的自然数
法1.暴力试除法
|
|
法2 一个因数出现 必然存在另一个因数 所有的约数是成对出现的既你n 能整除一个因子所得到的数 那你必然能整除刚整除得到的数
记为 d | n
, $\frac{n}{d} | n $ ,n能被d 整除 那么 n
也能被 $\frac{n}{d}$整除
也就是说 我们只需要枚举较小的那个因数 就必然能找到较大的那个因数。
所以要d <= n/d => d*d <=n ,但有可能爆int 所以改为除法好点
d <= sqrt(n)
|
|
埃氏筛质数
luoguP3383
质数x质数一定等于合数 ,因为该除了可以被1和自身整除 还可以被两个相同的质数整除 要不然你怎么相乘得到该数…
也就是说 得到的合数一定是该质数的倍数 既,质数的倍数一定是合数。
所以筛选质数的时候就可以把质数的倍数给剔除。剩下的就是质数
但是该方法的缺点是会重复剔除。 复杂度 o(N*loglogn) 近乎o(N).
复杂度 n/2 + n/3 +….+n/n = n * (1/2+1/3+…+1/n) 调和级数 = ln n + c(欧拉常数)
o(nln n) 优化:
但是上面是把每一个数的倍数都删掉,其实不用 根据整数惟一分解定理只需要把质数的倍数删掉即可(合数的就不用管了),。直接把下面的倍数扔去if里面
|
|
關於爲什麽要i*i
而不是i*2
当然也可以但是i*i
可跳过 如6
在2已被划 3就没必要划
证明:
从[i,i*i)这段区间可以被[2,i-1]
划 为什么?
根据整数唯一分解定理
$$
n=p_1^{\alpha_1} p_2{ }^{\alpha_2} \cdots p_s^{\alpha_s}, (p_1<p_2<p_3<…<p_n)
$$
反证 , i*i 分解后质数范围在[2,i-1] 里 所以可以交给之前的质数划,自己本身从i*i
出发即可
线性筛法(欧拉筛法)
P3912 素数个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
朴素筛法 使用质数筛选出来的合数 会有重复 而重复的根本原因是乘出来的合数可以被多个因数获得,而在相乘(加)的过程中所得到的合数因子有可能包含之前用来相乘的质数。也就意味着该合数是之前质数的倍数 意味着之前的质数累加 和当前质数的累加会有重复部分 如 6 这个合数 在埃氏筛里被2,3筛了两次
既要确保每一个合数只会被最小质因数筛掉 即可保证每个合数只会被筛选一次,先理解算法流程 待会再证明
注意到筛法求素数的同时也得到了每个数的最小质因子。
算法流程:
-
如果当前数没划掉 必定是质数 记录该质数(因为你一开始是从2开始 后面又经过筛选)
-
从小到大枚举当前已记录的质数,如果筛选的合数超过筛选的范围则中断
- 条件 i % p[j] == 0 ,
p[j]
也一定是i
的最小质因子(因为是从小到大枚举当前的质数)- 如果
i
是质数那么枚举到的p[j]
就是自身 中断 - 如果
i
是合数 那么最多枚举到自身的==最小质因数== 直接中断 防止重复标记.
- 如果
所以筛选的每一个数都是最小质因子得到,而根据惟一性定理,一个合数一定存在一个最小质因子, 也就意味着一个合数只被筛选了一次 既为线性.
- 条件 i % p[j] == 0 ,
在线性筛中 每个 合数m
都是被 最小质因子筛选掉的 其中 m = i * p[j]
而 p[j]
又是从小到大枚举,正因为是从小到大枚举质因子p[j]
所以可以拿到最小质因子 那么怎么拿到最小质因子 就是通过
i % p[j] == 0
这个条件
若i
能被pj
整除 那么pj
一定是 i
的最小质因子 因为在第二层循环中是从小到大枚举所有质数,一旦发现取余为0 那么 pj
就是 i
的最小约数,又因为该约数还是质数 所以就是i
的最小质因数,
同理也一定是m
的最小质因数 因为是从小到达枚举的质数 , 由于m = i*pj
得来 若不是m
的最小质因数 那么在前面的i
就已经被筛选掉
|
|
Q 会漏解吗?
A:
假设存在一个合数m没有被标记,那么m必然有一个最小质因数p。但是在遍历到p时,我们会标记p的所有倍数,包括m,所以矛盾。因此,任何合数都会被标记。
Q 为什么保证了最小质因子 就能保证唯一性?
A:
每个合数都会被它最小的质因数标记,因此在整个筛法过程中,每个质数只会被标记一次。如果一个数有多个质因数,那么它会在被最小的质因数标记后,就不再被其他质因数标记,因为其他质因数的倍数会在更早的时候被标记。
如果一个合数被多个质数筛选,那么它的最小质因子一定是其中一个质数,而其他合数都会在它的最小质因子筛选时被排除掉,因此不会重复筛选。因此,只要保证每个合数只能被它的最小质因子筛选,就能保证每个合数只被筛选一次。
Q 会不会有质数被当成合数筛(划)掉?
A
不可能, 因为 m 是 通过 i*pj
得来, 约数显然不只一个 而第一层循环又从2开始,怎么相乘都不可能得到质数
代码参考