质数筛法是用于找出一定范围内所有质数的算法。质数也叫素数，是指只有1和它本身两个约数的自然数，0和1既不是质数也不是合数。首先根据质数的定义，可以提炼出以下几点内容
- 素数是自然数，因此是整数
- 素数是大于1的自然数，因此小于等于1的数字都不是素数（包括负数，0和小数）
- 素数只有两个因数，1和自身
结合1,2,3点，可以推断出，在自然数范围内，最小的素数是2。
筛质数的方法主要有三种：朴素筛法、埃氏筛法（埃拉托色尼筛法）和欧拉筛法。以下是这三种方法的详细归纳总结：
朴素筛法 朴素筛法直接根据质数的定义来判断一个数是否为质数。它从2开始遍历到n，对于每个数i，检查是否有比i小的数能够整除i。如果没有，那么i就是质数。朴素筛法的时间复杂度较高，为O(n^2)。
代码模板如下：
// 定义一个函数来判断一个整数n是否为质数
bool isPrime(int n) {
// 如果n小于2，直接返回0，因为0和1都不是质数
if (n < 2) return 0;
// 初始化一个变量tmp，用于存储n-1，因为只需要检查到n-1的因子
int tmp = n - 1;
// 从2开始遍历到tmp（即n-1），检查是否有数能整除n
for (int i = 2; i <= tmp; i ) {
// 如果n能被i整除，说明n不是质数，返回0
if (n % i == 0) {
return 0;
}
}
// 如果循环结束后没有找到能整除n的数，说明n是质数，返回1
return 1;
}
// 主函数，用于遍历从2到n的所有整数，并打印出所有质数
int main() {
// 假设n是我们要筛选的数的范围上限
int n; // 这里需要定义n的值，例如：n = 100;
// 遍历从2到n的所有整数
for (int i = 2; i <= n; i ) {
// 使用isPrime函数判断当前的i是否为质数
if (isPrime(i) == 1) {
// 如果是质数，打印出来
printf("%d ", i);
}
}
return 0; // 主函数返回0表示程序正常结束
}
同时可在此基础上更进一步：一个数去除以比它的一半还要大的数，一定除不尽的，所以只需要除到n/2即可。
// 初始化一个变量tmp，用于存储n/2，因为只需要检查到n/2的因子
int tmp = n / 2;
再进一步：一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中也不需要遍历到n/2，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。因此只要从2枚举到 √n即可。
// 初始化一个变量tmp，用于存储 √n，因为只需要检查到 √n的因子
int tmp = sqrt(n);
⭐值得注意的是，此时的时间复杂度是O(n^(3/2))
埃氏筛法（埃拉托色尼筛法） 埃氏筛法是一种更高效的筛法，它基于一个原理：一个合数总是可以分解成若干个质数的乘积。算法步骤如下：
- 初始化一个布尔数组，表示每个数是否为质数（true表示质数，false表示非质数）。
- 从2开始，将当前最小的质数的倍数标记为非质数。
- 重复步骤2，直到遍历到n。
埃氏筛法的时间复杂度为O(n log log n)，因为它避免了对每个数进行多次筛选。
代码模板如下：
// 定义一个常量maxn，表示筛法的最大范围
const int maxn = 1e7;
// 创建一个布尔数组IsPrime，用于标记每个数是否为质数（true表示质数，false表示非质数）
bool IsPrime[maxn];
// 创建一个整数数组prime，用于存储筛选出的质数
int prime[maxn];
// 定义一个函数Era_prime，用于执行埃氏筛法并返回质数的个数
int Era_prime(int n) {
// 初始化计数器tot，用于记录找到的质数个数
int tot = 0;
// 使用memset函数初始化IsPrime数组，将所有数标记为质数（true）
memset(IsPrime, true, sizeof(IsPrime));
// 将0和1标记为非质数（false）
IsPrime[0] = false;
IsPrime[1] = false;
// 从2开始遍历到n，执行筛法
for (int i = 2; i <= n; i ) {
// 如果当前数i被标记为质数（IsPrime[i]为true）
if (IsPrime[i]) {
// 将当前质数i添加到prime数组中，并更新质数计数器tot
prime[tot ] = i;
// 从i的2倍开始遍历，将i的所有倍数标记为非质数（false）
for (int j = i * 2; j <= n; j = i) {
IsPrime[j] = false;
}
}
}
// 返回找到的质数总数
return tot;
}
这段代码实现了埃氏筛法，它是一种高效的质数筛选算法。通过遍历从2到n的所有整数，并标记所有已知质数的倍数为非质数，从而筛选出所有质数。这种方法的时间复杂度为O(n log log n)，比朴素筛法的O(n^2)要高效得多。在实际应用中，这个函数可以用来找出1到n之间所有的质数。
欧拉筛法
欧拉筛法是埃氏筛法的优化版本，它只对每个数进行一次筛选。算法的核心思想是，每个合数只会被它的最小质因数筛去。
与此想法相同，有一个定理叫算术基本定理（唯一分解定理）：任何合数都能表示为若干质数的乘积，且该分解因式是唯一的。（不考虑顺序性）
原理：规定每个合数只会被它最小的质因数筛去。（后面的质因数直接跳过），这个最小的质因式必定小于它本身。
算法步骤如下：
- 初始化一个布尔数组，表示每个数是否为质数。
- 从2开始，对于每个质数i，将其倍数标记为非质数，但只到i的平方根。
- 如果在标记过程中发现i能被某个质数整除，那么跳过这个质数，因为i已经被之前的质数筛去了。
欧拉筛法的时间复杂度为O(n)，因为它在每个数上只进行一次操作，大大减少了计算量。
代码模板如下：
// 定义一个常量maxn，表示筛法的最大范围
const int maxn = 1e7;
// 创建一个布尔数组IsPrime，用于标记每个数是否为质数（true表示质数，false表示非质数）
bool IsPrime[maxn];
// 创建一个整数数组prime，用于存储筛选出的质数
int prime[maxn];
// 定义一个函数Euler_prime，用于执行欧拉筛法并返回质数的个数
int Euler_prime(int n) {
// 初始化计数器tot，用于记录找到的质数个数
int tot = 0;
// 使用memset函数初始化IsPrime数组，将所有数标记为质数（true），0和1标记为非质数（false）
memset(IsPrime, true, sizeof(IsPrime));
IsPrime[0] = false;
IsPrime[1] = false;
// 从2开始遍历到n，执行欧拉筛法
for (int i = 2; i <= n; i )
{
// 如果当前数i被标记为质数（IsPrime[i]为true）
if (IsPrime[i])
{
// 将当前质数i添加到prime数组中，并更新质数计数器tot
prime[tot ] = i;
// 遍历已经找到的质数列表
for (int j = 0; j < tot; j )
{
// 如果i乘以当前质数列表中的质数prime[j]的结果大于n，跳出内层循环
if (i * prime[j] > n)
{
break;
}
// 将i的倍数标记为非质数（false）
IsPrime[i * prime[j]] = false;
// 如果i能被prime[j]整除，说明i已经被筛过了，跳出内层循环
if (i % prime[j] == 0)
{
break;
}
// 由于prime数组中的质数是从小到大排列的，所以i乘以其他更大的质数的结果
// 一定会被prime[j]的倍数筛掉，因此可以直接跳出内层循环
}
}
}
// 返回找到的质数总数
return tot;
}
这段代码实现了欧拉筛法，它是埃氏筛法的一个优化版本。欧拉筛法的核心思想是，对于每个合数，只筛选出它的最小质因数，这样可以避免重复筛选。这种方法的时间复杂度为O(n)，因为它在每个数上只进行一次操作，大大减少了计算量。在实际应用中，这个函数可以用来找出1到n之间的所有质数。
