START:
暴力
从 1 - n
想法
按照素数的定义来嘛,除了 1 和它本身没有别的因子,就是素数
代码
1 | for(int i = 2; i < n; i++) |
特点
辣鸡算法,n
稍微大一点就慢慢等吧。
从 1 - sqrt(n)
想法
因子都是成对出现的,并且均匀地分布在 sqrt(n)
周围,所以只需要比一半。
代码
1 | for(int i = 2; i < sqrt(n); i++) |
特点
还是辣鸡,容易爆。
普通筛
埃氏筛
想法
素数的倍数一定不是素数。
实现
用一个 n+1
长度的bool
数组is_prime
保存,从第一个素数 2
开始,置其倍数为true
一直到大于 n
然后继续下一趟。
代码
1 | int is_prime[n] = {0}; |
特点
时间复杂度O(nloglogn)
空间复杂度 O(n)
标记过一边的东西又被标记一边,感觉好蠢,为啥不能直接把第二个for j
放到if
里去?
验证发现可以,但是用时差不多。
线性筛
想法
每个合数只会被它的最小质因子筛去,因此每个数只会被标记一次,所以复杂度为O(n)
。
代码
1 | int is_prime[maxn] = { 0 }; |
证明
先决条件:
- 任何合数等于一系列素数的积,即一个特定的素数序列可以决定任意一个合数,这种关系可以被定义为一种映射。
不论 i
是否是素数,都会执行到第 12 行的 for
循环:
如果
i
是素数,两个素数所组成的素数序列一定是特异的,我们将这个序列叫做p
。如果
i
是合数,就可以把它看成一组素数序列,并在其末尾增加一个p[j]
,虽然这个序列的顺序并不影响映射关系,但为了方便研究,使其有序,并令p
这个序列是一个递增的序列。因此可以知道,
p[0]
是序列p
中的最小值。根据第 21 行,当
is_prime[j]
能够被i
整除的时候,且is_prime
序列是递增排列的,我们可以得到一个结果:此时
is_prime[j]
即为序列p
中的p[0]
。那么就可以说明,第 21 行代码只能筛出不大于
p[0]
的素数。
证明举例
假设序列p
的元素有p0 = {2,3,5}
,这个序列可以筛出2*i
而不能筛出3*i
。
如果能够筛出3*i
,那么当p1 = {3,3,5}
时,必定会重复标记。
参考
线性筛求素数-Grubbyskyer 暴力部分,普通筛中埃氏筛全部,线性筛除证明和证明举例部分。
一般筛法求素数+快速线性筛法求素数-dinosoft 线性筛中证明和证明举例部分。