筛选质数的三种方法：素数判断、埃氏筛法和欧拉筛法
筛选质数的三种方法：素数判断、埃氏筛法和欧拉筛法
在计算机科学和数学领域，质数（素数）的筛选是一个经典且重要的问题。本文将详细介绍三种筛选质数的方法：素数判断、埃氏筛法和欧拉筛法。通过对比这些算法的原理、优势和不足，帮助读者更好地理解质数筛选的实现方式。
一、素数是什么？
素数（Prime number），又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。换句话说，一个大于1的自然数，如果只能被1和它本身整除，那么这个数就是素数。例如，2、3、5、7、11等都是素数，因为它们都只能被1和它们自己整除。而4、6、8、9等则不是素数，因为它们除了1和自身外，还能被其他自然数整除。
素数在数论中扮演着非常重要的角色，许多数学定理和猜想都与素数有关。例如，著名的哥德巴赫猜想就断言每一个大于2的偶数都可以写成两个素数之和。此外，素数也是加密技术中广泛使用的数学工具，如RSA加密算法就依赖于大素数的生成和分解的困难性。
二、算法使用原理
1. 合数
合数除了1和它本身以外，还有其他因数。与素数相对，素数只有1和它本身两个因数，而合数则至少有三个因数。
2. 埃氏筛法的核心思想
我们理解了合数的概念后，可以知道一个合数可以由至少三个因数构成，如6=123，说明所有素数的倍数都可以是合数。因此，埃氏筛法就是利用这个原理将所有合数标记。
三、埃氏筛法
定义与背景
埃拉托斯特尼筛法（Sieve of Eratosthenes），简称埃氏筛法，是一种简单且年代久远的筛法，用来找出一定范围内所有的素数。该算法由古希腊数学家埃拉托斯特尼提出，是一种基于素数的性质进行筛选的算法。
核心原理
- 初始化：首先，将待筛选范围内的所有数都视为潜在素数（通常使用一个布尔数组来表示，数组的下标对应自然数，数组的值表示该下标对应的数是否为素数，true表示是素数，false表示不是素数）。
- 筛选过程：
- 从最小的素数2开始，将其所有的倍数（除了2本身）都标记为非素数（即将对应数组位置的值设为false）。这是因为素数的定义是只能被1和自身整除的数，所以任何素数的倍数都不可能是素数。
- 接着，找到下一个未被标记为非素数的数（即下一个素数），重复上述过程，继续标记其所有倍数为非素数。
- 这个过程一直持续，直到遍历完所有待筛选的数或者当前素数的平方大于待筛选范围的最大值时停止。因为如果一个合数n有除了1和它本身以外的因数，那么这些因数中必然有一个不大于sqrt(n)（算术基本定理）。所以，当一个素数的平方大于待筛选范围的最大值时，就可以确定剩下的数都是素数了。
- 结果输出：最后，未被标记为非素数的数就是素数，可以通过遍历布尔数组来输出这些素数。
算法优势与不足
优势：
- 相对于其他简单的素数筛选方法（如试除法），埃氏筛法能够更快速地找出一定范围内的所有素数。
- 算法实现简单，易于理解和编程。
不足：
- 当筛选范围较大时，虽然算法的时间复杂度相对较低（接近O(nloglogn)），但空间复杂度较高，需要额外的空间来存储每个数的状态。
- 算法在筛选过程中可能会重复标记某些数为非素数（例如，一个数可能会同时被多个素数的倍数所标记），这虽然不影响最终结果的正确性，但会增加一些不必要的计算量。
代码展示
其中的 j=i*2 可以改成 i*i，因为写法不一样，原因是因为 1*2*3 和 1*3*2 的答案是一样的，所以用 i*2 会造成重复，但是影响不大，注意方便理解。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n; // 范围2-n
int prime[n+1]={0}; // 标记数组，可以用 bool prime[n+1]
int ans=0;
for(int i=2;i<=n;i++)
{
if(!prime[i]) // 如果是素数
{
for(int j=i*2;j<=n;j=j+i) // 素数的倍数都是合数，原因在开始介绍了。为什么是 j=j+i 因为是倍数增加。注意改变的是 j 不是 i。i 相当于素数 i*2 就是一倍。
{
prime[j]=1; // 对合数进行标记。
}
}
}
for(int i=2;i<=n;i++) // 遍历，没有标记的就说素数
{
if(prime[i]==0) ans++;
}
cout<<ans;
return 0;
}
// 优化版； 对答案的储存进行了优化，利用了前缀和。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int prime[n+1]={0}; // 标记
int sum[n+1]={0};
int ans=0;
for(int i=2;i<=n;i++)
{
if(!prime[i]) // 如果是素数
{
sum[i]=sum[i-1]+1; // 前缀和求当前位置的素数有多少个
for(int j=i*2;j<=n;j=j+i) // 核心 标记合数 如 12=2*2*3; 12=2*6; <=n 表面不超过最大范围
{
prime[j]=1;
}
}
else
{
sum[i]=sum[i-1]; // 如果不是素数继承前面的状态。
}
}
cout<<sum[n];
return 0;
}
四、欧拉筛法
面对埃氏法的不足，我们又衍生出一种优化的算法——欧拉筛法。
欧拉筛法选素数的核心思想
欧拉筛法的核心思想在于确保每个合数只被其最小的质因子筛掉一次，从而避免了重复筛选，提高了算法的效率。具体来说，当遍历到一个数 i 时，欧拉筛法会使用小于等于 i 的所有已知质数 prime[j] 去筛 i*prime[j]（其中 j 从0开始，且 prime[j]≤sqrt(i)），但这里有一个关键优化：当 i 能被 prime[j] 整除时（即 i%prime[j]==0），就停止用更大的质数去筛 i 的倍数。这是因为如果继续用更大的质数筛，那么筛掉的将是 i 的倍数与更大质数的乘积，而这个乘积的最小质因子仍然是 prime[j]，这会导致重复筛选（下面避免重复筛选解释了）。注意储存素数的数组是递增的，所有要从头遍历，才能保证被最小质因数筛掉。
欧拉筛法在埃氏筛法上的优化
- 避免重复筛选：
- 埃氏筛法中，一个合数可能会被它的多个质因子重复筛选多次（例如，30=215=310=5*6，在埃氏筛法中，30会被2、3、5都筛一遍）。而欧拉筛法通过确保每个合数只被其最小的质因子筛掉一次，从而避免了这种重复筛选。（解决方法就是开了一个数组储存素数）
- 时间复杂度降低：
- 埃氏筛法的时间复杂度为 O(nloglogn)，而欧拉筛法由于避免了重复筛选，其时间复杂度接近 O(n)，是一种非常高效的质数筛选算法。
- 实现方式：
- 欧拉筛法通常采用两个数组：一个用于存储质数（prime数组），另一个用于标记一个数是否已经被筛掉（vis数组或类似的标记方式）。遍历从2到n的所有数，对于每个数i，如果它还未被筛掉（即是质数），则将其加入到prime数组中，并用prime数组中的每个质数去筛 i 的倍数，但遵循上述的关键优化。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int prime[n+1]={0};
int sum[n+1]={0};
int ans=0;
for(int i=2;i<=n;i++)
{
if(!sum[i]) prime[ans++]=i; // 储存素数的数组。
for(int j=0;j<ans;j++)
{
if(prime[j]*i>n) break;
sum[prime[j]*i]=1;
// 这一步的解释，这里的 i 表示的不是素数，还是利用合数 = 1*x*y
// 埃氏法是固定素数 x, 遍历 y，而欧拉筛是固定 y，就是这里的 i，遍历素数数组，这
// 就是我们为什么要存放素数
if(i%prime[j]==0) break; // 判断是否能被最小质因数整除；
// 避免重复筛选，文章内有解释。
}
}
cout<<ans;
return 0;
}
总结
欧拉筛法通过避免重复筛选，在埃氏筛法的基础上实现了时间复杂度的显著降低，是一种高效且实用的质数筛选算法。其核心思想在于确保每个合数只被其最小的质因子筛掉一次，从而提高了算法的效率。在实际应用中，欧拉筛法在处理大规模数据时表现出色，被广泛应用于密码学、数论、组合数学等领域。
题目展示：来自力扣的3233题
思路
根据题意，文章让我们找特殊数字，这个数字有三个因数，那么什么数只有有三个因数呢，肯定是质数的平方了，所有题目的真正意思是让我们找这个范围内质数的平方，如何简便运算呢，首先让我们找平方，那么可以先缩小范围，找可以开根号的数里面的质数，第一步就可以对范围进行预处理，然后套我们的素数筛选方法。
代码
写法二
喜欢偷懒。其实就是换欧拉筛法，主体都是一样的，优化版本也是，靠各位编程之星自己解决了，留点思考量。