定义法
素数的定义：
- 只能被1和本身整除的数。
适用范围：
- 适合判断单个数是否为素数
- 若是求一个大范围内的所有素数，此方法耗时太长
代码：
/*判断n是否为素数*/
for(i=2;i*i<=n;i++) {
if(n%i==0) {
flag=0;/*flag=0代表n不是素数*/
break;
}
}
普通筛选法/埃氏筛法
思想：
- 首先假定所求范围内的所有数都是素数，然后去除该范围内的所有合数，剩下的全是素数。
- 任何合数均可表示为素数的倍数。因此，如果已知一个数是素数，那么它的倍数都是合数。
代码：
int not_prime[MAXN]={0};/*假定所有数都是素数*/
for(int i=2;i<=sqrt(MAXN);i++) {
if(!not_Prime[i]) {/*如果i是素数*/
for(j=i*i;j<=MAXN;j+=i) {/*那么i的倍数全是合数*/
not_prime[i]=1;
}
}
}
注意事项：
- 为什么第二重循环里j的初始值为i* i呢？这是为了避免重复标记。举个例子，若i是素数，那么2* i、3* i、4* i……（i-1）* i分别是2、3、4……（i-1）的倍数，在外层循环循环到i之前就已经被标记为合数了。所以应该从j=i* i开始，依次把j+i、j+2* i……标记为合数。
缺陷：
对于一个合数，可能被重复筛选多次。
线性筛选法/欧拉筛法
思路：
欧拉筛法是埃氏筛法的改进版，大体思路都是先假定所有数都是质数，然后把所有合数去除，留下的都是质数；不同之处就是去除合数的方法，欧拉筛法保证了每个合数只会被它的最小质因数筛去。虽然代码有两重循环，但是因为待求范围内的每个数均只被筛选1次，所以时间复杂度是O(n)。
代码：
bool visit[MAXN]={0};/*visit数组存的是待求范围的所有自然数*/
/*visit[1]=0表示1是素数*/
int prime[MAXL]; /*prime数组只存待求范围内的素数*/
/*MAXL可以根据MAXN的大小大致估计一下，MAXN一般是题目给出*/
int cnt=0; /*cnt用来记录素数的个数*/
void getprime(int n)
{
for(int i = 2;i <= n;i++) {
if(!visit[i]) prime[cnt++]=i;/*如果i是素数，就把i标记在prime数组里*/
for(j = 0;i * visit[j] < n && j < cnt;j++) {
visit[i * prime[j]] = 1;/*prime数组里面存的素数的i倍，都标记为合数*/
if(i % prime[j] == 0) break;/*关键，看后面的解释*/
}
}
}
``
### 解释：
为什么说欧拉筛法保证了每个合数只会被它的最小质因数筛去呢？
关键是这一行：
```c
if(i % prime[j] == 0) break;
接下来分类讨论一下：
- 如果i % prime[j] ！= 0，prime[j]一定小于i的最小质因数，所以prime[j]一定是i* prime[j]的最小质因数。
- 如果i % prime[j] == 0，
（1）prime[j]就是i的最小质因数（因为j是从小到大枚举的），此时prime[j]依旧是是i* prime[j]的最小质因数。
（2）但是j++后的下一个prime[j]，就大于i的最小质因数，故prime[j]不是i* prime[j]的最小质因数。所以才要在i % prime[j] == 0的时候break。