主要讲解怎么判断一个数字是否是素数：
埃式筛
学习埃氏筛之前，我们先看一下暴力筛法，即对每个数都用试除法判断其是不是质数：
暴力筛法：
# include <stdio.h>int main()
{int st[N]; // 初始化为0， 0表示质数，1表示合数for(int i = 2; i <= n; i++){for(int j = 2; j <= i / j; j++){//试除法if(i % j == 0){st[i] = 1; // 合数，标记为1 }}
}
这种方式无疑是最慢的，我们看一下如何加快，换一种思路：一个质数的倍数一定是合数，所以，假设P是质数，那么就可以筛选掉2~100之间所有P的倍数。
先看个例子，对于数列1~11：
先筛去2的倍数：
然后筛去3的倍数：
然后筛去5的倍数：
至此，1~11内的所有合数都被筛完了， 2 3 5 7 11是数列中的质数。
为什么这样能筛去所有的合数呢，因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。
埃氏筛代码：
# include <stdio.h>
int main()
{int n = 100;int st[100] = {0};for (int i=2; i<=n; ++i){if (st[i] == 0){for (int j=2*i; j<=n; j=j+i)st[j] = 1;// j是i的一个倍数，j是合数，筛掉。}}
}以上的时间复杂度为
我们还可以对其进行优化：
1.我们会先筛2的所有倍数，然后筛3的所有倍数，但筛除3的倍数时，我们还是从3的2倍开始筛，其实3 * 2 ，已经被2 * 3时筛过了。
又比如说筛5的倍数时，我们从5的2倍开始筛，但是5 * 2会先被2 * 5筛去， 5 * 3会先被3 * 5会筛去，5 * 4会先被2 * 10筛去，所以我们每一次只需要从i*i开始筛，因为(2，3,…,i - 1)倍已经被筛过了。
优化后的埃式筛：
# include <stdio.h>
# include <math.h>
int main()
{int n = 100;int st[100] = {0};for (int i=2; i<=int(sqrt(n)); i++){if(st[i] == 0){for(int j = i * i; j <= n; j += i)st[j] = 1; // j是i的一个倍数，j是合数，筛掉。}}
}优化后的时间复杂度可以近似看成O ( n ) 了。
但是，我们还可以更快，那就是欧拉筛。
欧拉筛
欧拉筛，又称为线性筛，时间复杂度为O ( n )
欧拉筛之所以能这么快，是因为不重复筛选，特点是合数都是被它的最小质因子筛去的
代码：
# include <stdio.h>
# include <stdio.h>int main()
{int n = 100;int st[100];//用于表示i是否是素数，如果是则为1，不是则为0for (int i=0; i<100; ++i)st[i] = 1;// 初始化int primes[100];//用于存储素数。int k = 0;for (int i=2; i<=int(sqrt(n)); ++i){if (st[i] == 1){primes[k] = i;k = k + 1;}for (int j=0; j<k; ++j){st[primes[j]*i] = 0; //筛去合数 if (i % primes[j] == 0) // 若 primes[j]是（合数）i的最小素因子，结束本轮遍历，防止重复标记 break;}}
} 欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。
可以参考对欧拉筛的解释视频：
欧拉筛，几行就行，一次就好_哔哩哔哩_bilibili
https://www.bilibili.com/video/BV1LR4y1Z7pm/?spm_id_from=333.337.search-card.all.click&vd_source=617dcf7ed08ed9625bdfcadc93c4fac7
