素数的判定
这个是挺早之前的了，发现没有更新到文档里，那就浅浅水一篇（主要是群友都在 push）（我的笔记还可以水超级多篇）。归档到这里，方便以后拿板子。
简介
素数又称质数，是指一个大于 1 的正整数，如果除了 1 和它本身以外，没有其他的约数，例如 2,3,5,7,3021377 等，反之就是合数。1 既不是素数也不是合数。
素数就像整数世界里的原子，整个整数世界都是由这些素数原子组成的，比如 15=3\times 5 ，121=11\times 11 等等。有关素数的问题是数论研究的主要课题，我国著名数学家华罗庚教授及陈景润、王元研究员、潘承洞教授等对素论的研究都有重要贡献.
早在 2000 多年前的古希腊，伟大的数学家欧几里德就用反证法证明了：素数有无穷多个。在他的不朽名著《几何原本》第四卷命题 20 中是这样叙述的：预先给定几个素数，则有比他们更多的素数。他是这样证明的：设 a,b,c 是给定的素数，构造一个新的数 t=a\times b\times c+1 ，则已有的素数 a,b,c 均不能整除 t ，所以要么 t 本身就是素数，此时 t 不等于 a,b,c 中任意一个数；要么 t 能被不同于 a,b,c 的某一个素数整除，因此必然存在一个素数力不同于已有的素数 a,b,c 。例如：2\times 3\times 5+1=31,3\times 5\times 7+1=106=2\times 53 。也就是说，有了 n 个素数，就可以构造出第 n+1 个素数，因此素数有无穷多个。
埃式筛法
对于数据范围比较大的情况下，需要找出所有素数，可以采用“筛选法”求出“素数
表”。具体方法如下：
-
先将 2\sim N 之间的所有数写在纸上：
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24\cdots
-
在 2 的上面画一个圆圈，然后划去 2 的其他倍数；
-
第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍数；
-
现在既未画圈又没有被划去的第一个数是 5 ，将它画圈，并划去 5 的其他倍数……
-
依次类推，一直到所有小于或等于 N 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N 的素数。实现代码如下：
//埃式筛法
#include <bits/stdc++.h>
using namespace std;
bool isprime[10000000];
void sieve(int n)
{
memset(isprime,true,sizeof(isprime));
for(int i=2;i*i<=n;i++)
{
if(isprime[i])
{
for(int j=i*i;j<=n;j+=i)
if(isprime[j])
isprime[j]=false;
}
}
}
int main()
{
int n;
scanf("%d",&n);
sieve(n);
for(int i=2;i<=n;i++)
if(isprime[i])
printf("%d ",i);
return 0;
}
欧拉筛法
仔细分析上述代码发现，这种方法会造成重复筛除合数，影响效率。比如 30 ，在 i=2 的时候，k=2\times 15 筛了一次；在 i=5,k=5\times 6 的时候又筛了一次。所以，也就有了“快速线性筛法”。快速线性筛法没有冗余，不会重复筛除一个数，所以“几乎”是线性的，虽然从代码上分析，时间复杂度并不是 O(n) 。先看实现代码：
//欧拉筛法
#include <bits/stdc++.h>
using namespace std;
bool isprime[10000000];
int prime[5000000];
void Euler_sieve(int n)
{
memset(isprime,true,sizeof(isprime));
prime[0]=0;
for(int i=2;i<=n;i++)
{
if(isprime[i])
prime[++prime[0]]=i;
for(int j=1;j<=prime[0] && i*prime[j]<=n;j++)
{
isprime[i*prime[j]]=false;
if(i%prime[j]==0)
break;
}
}
}
int main()
{
int n;
scanf("%d",&n);
Euler_sieve(n);
for(int i=1;i<=prime[0];i++)
printf("%d ",prime[i]);
return 0;
}
首先，先明确一个条件，任何合数都能表示成一系列素数的积。
- 如果 i 是素数的话，那简单，一个大的素数 i 乘以不大于 i 的素数，这样筛除的数跟之前的是不会重复的。筛出的数都是 n=p_1\times p_2的形式，p_1 和 p_2 不相等；
- 如果 i 是合数，此时 i 可以表示成递增素数相乘 i=p_1\times p_2\times \cdots \times p_n ，p_i 都是素数 (2\leq i\leq n),p_i\leq p_j(i\leq j) ，p_1 是最小的系数。
根据上述代码，当 p_1==\text{prime}[j] 的时候，筛除就终止了，也就是说，只能筛出不大于 p_1 的质数\times i 。
我们可以直观地举个例子。i=2\times 3\times 5 ，此时能筛除 2\times i，不能筛除 3\times i ，如果能筛除 3\times i 的话，当 i'=3\times 3\times 5 时，筛除 2\times i' 就和前面重复了。
当然，还有 2 个结论是可以证明的：
- 一个数不会被重复筛除；
- 合数肯定会被筛除。
参考资料：
- 林厚从《信息学奥赛 之 数学一本通》
评论区