如果你想要判断一个数字是否是质数，你该怎么办呢？

首先，我们要先知道质数的定义是什么：

质数是指，在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

那么我们很简单就能编辑出我们的最初版判断素数函数：【我们以欧拉第七题举例，输出第10001个素数】

#include <iostream>
#include <cmath>
#include <cstdio>//头文件
using namespace std;
#define MAXN 200000//一个宏定义，来定义最大值MAXN，方便修改
int prime[20000];
bool judge_prime(int x) {//声明一个函数，用来判断是否是质数
	for (int i = 2; i <= sqrt(i); i++) //循环到根号下i为止，因为i是最大值
    {
		if(x % i == 0)return false;//如果有除了2以外的数是他的因子，则不是质数
	}
	return true;//如果没有除了2以外的因子，则是质数
}

int main()
{
	int cnt = 0, i = 2;//声明一个变量cnt用于记录当前素数的个数，声明i为当前判断的数的值
	for(int i = 1; i <= MAXN; i++){//循环到MAXN结束
		if(judge(i)){//如果i是质数
			cnt++;//cnt++
			prime[cnt]=i;//把数组的第cnt位记为i
		}
	}
	cout << prime [10001];//输出标记数组里的第10001位，也就是第10001个素数。
	return 0;
}

懂了？

但是这样比较麻烦

我们还有下一种办法：素数筛

又称欧拉筛

我们利用素数来标记合数

因为合数一定有质因子

所以我们从最小的质数出发

标记所有它的倍数，到MAXN为止

然后i++，如果这个数字被标记过，那么它就是合数

如果这个数字没有被标记过，那么他就是质数

然后我们就要去标记他的倍数

以此类推。

话不多说，上代码！

#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 200000
int prime[MAXN];//声明一个prime[MAXN]，且初识为0
void list_prime() {//声明一个
	for (int i = 2; i <= MAXN; i++) {//循环MAXN次
		if (prime[i])continue;//如果prime[i]中已经有了值(也就是被标记过)，则直接进行下一个循环
		prime[0]++;//我们用prime数组的第0位来进行计数。所以这一步就是计数器++
		prime[prime[0]] = i;//primt[计数器]赋值为i(这个数的大小)
		for (int j = i * 2; j <= MAXN; j += i) {
			prime[j] = i;//标记i的倍数
		}
	}
	return;//结束函数
}

int main()
{
	list_prime();//调用我们的素数筛函数
	printf("%d\n", prime[10001]);//输出标记数组里的第10001位，也就是第10001个素数。
	return 0;
}

这个方法比上一个好了很多。

但是还有一个小问题：

很多数字标记了好几次，有不必要的时间开销。

比方说：

15这个数字，我们在3里面标记了一次；5里面也标记了一次。

所以，我们还能继续简化：

对于一个数字n，我们从2开始标记，每次往后移动一个质数，一直标记到n的最小质因数

也就是从2 * n一直到n的最小质因数 * n

然后n++，继续向下标记。

举个例子：

从2开始，到2的最小质因数2。

也就是只标记一个2*2，等于4。

对于3，从2开始标记，标记到3的最小质因数3。

也就是标记一个3 * 2，3 * 3，即6和9。

对于4，我们从2开始标记，标记到4的最小质因数2。

也就是只标记一个2 * 4，即8。

对于5，我们从2开始标记，标记到5的最小质因数5。

也就是标记5 * 2，5 * 3，5 * 5，即10，15，25。

对于6，我们从2开始标记，标记到6的最小质因数2

也就是6 * 2，只有一个数字12。

对于7，同理，标记14，21，35（但是我们只以前30个举例子，你可以理解为MAXN=30。后续将不再进行超出30的举例）

对于8，同理，标记16。

对于9，同理，标记18，27。

对于10，同理，标记20。

对于11，标记22；

对于12，标记24；

对于13，标记26；

对于14，标记28；

对于15，标记30。

然后我们发现，所有合数只被标记了一次，我们就得到了下面的素数表：

上代码！

#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 200000
int prime[MAXN+100];//声明一个数组，用来存储质数、声明质数
void list_prime() {//声明线性筛函数
	for (int i = 2; i <= MAXN; i++)//循环到MAXN停止
	{
		if (!prime[i])//因为prime[i]的初值位0，所以加了一个叹号。这样的话，被标记过为假，没被标记过为真
		{
			prime[0]++;//还是用prime[0]来做计数器，计数器++
			prime[prime[0]] = i;//把prime[计数器]赋值为i
		}

		for (int j = 1; j <=prime[0]; j++)
		{
			if (prime[j] * i > MAXN)break;//如果标记的值已经超过了MAXN，那就退出
			prime[prime[j] * i] = 1;//把 prime[j](用来标记的质数，从2（prime[i]）开始，到最小质因数结束。) * i(用来标记的数字，也就是2、3、4、5....) 这一位标记为1。
			if (i % prime[j] == 0)break;//如果i % prime[j]为0，那prime[j]就不是最小质因数了，退出循环。
		}
	}
}

int main()
{
	list_prime();//调用这个函数
	cout << prime[10001];//输出他的第10001位
	return 0;
}