欧拉筛选法求质数的算法解析

正常的埃氏筛选法是定义一个bool型的数组，把所有数组的元素初始化为1.表示初始阶段所有数都是质数。开始对数组进行筛选，把所有含有2和2的倍数的所有数筛选掉。在把所有含有3和3的倍数的所有数筛选掉，再把含有5和5的倍数的所有数筛选掉.一直筛选到只剩下素数为止。

#include <bits/stdc++.h> using namespace std; bool f[10001]; // 标记数组，f[i] = true 表示 i 是素数 // 埃氏筛法函数，筛选出 1 到 n 之间的素数 void primer(int n) { memset(f, true, sizeof(f)); // 初始假设所有数都是素数 f[1] = false; // 1 不是素数 int x = sqrt(n); // 只需要筛到 sqrt(n) 即可 for (int i = 2; i <= x; i++) { if (f[i]) { // 如果 i 是素数 // 标记 i 的所有倍数为非素数 for (int j = 2; j <= n / i; j++) { f[i * j] = false; } } } } int main() { int a, b, sum = 0; cin >> a >> b; // 输入区间 [a, b] primer(b); // 筛选出 1 到 b 之间的素数 for (int i = a; i <= b; i++) { if (f[i]) { sum++; // 统计区间内素数个数 } } cout << sum << endl; // 输出结果 return 0; }

其中欧拉筛选法是在埃氏筛选法基础上，让每一个合数，之被他的最小质因数筛选一次。以达到不重复的目的。对于一个合数的分解：将其分解为他的最小质因子与一个其他数的乘积。

欧拉筛法的判断：如果i是质数，那么就将它与之前的质数（包括它本身）的乘积筛掉 。 如果i是合数，那么就将它与从2到它最小的质因子之间的质数的乘积分别筛掉。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e8 + 5; bool f[MAXN]; // f[i] = true 表示 i 是素数 int a[MAXN]; // 存素数 int sum = 0; // 素数个数 int n; int main() { cin >> n; // 初始化 f 为 true（除了 0 和 1） for (int i = 2; i <= n; i++) f[i] = true; for (int i = 2; i <= n; i++) { if (f[i]) { a[++sum] = i; // 记录素数 } for (int j = 1; j <= sum && i * a[j] <= n; j++) { f[i * a[j]] = false; if (i % a[j] == 0) break; // 保证每个合数只被标记一次 } } cout << sum << endl; return 0; }

对于a[++sum] = i;这行代码的含义是从1开始记录每一个素数的值。不重复