定义法

素数的定义：

• 只能被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;

接下来分类讨论一下：

1. 如果i % prime[j] ！= 0，prime[j]一定小于i的最小质因数，所以prime[j]一定是i* prime[j]的最小质因数。
2. 如果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。

学自大佬，欢迎交流批评指正。