C++数学-数论筛质数经典OJ题流食般投喂

先做题自己思考，再看解析呦~

OJ题来源：洛谷

OJ题名：素数密度

OJ题归属：数学-数论【筛质数】

解题算法：线性筛、埃氏筛

🐻算法原理：

🐻借助素数的判定中用试除法从 [1，sqrt r] 进行试除的原理，在筛质数里面，我们可以用 [1，sqrt r] 中的质数去筛掉 [l，r] 里面的合数。

🐻在对区间 [l，r] 进行筛质数时，要合理映射下标~

🐻筛质数时，我们要从质数的 “合理倍数” 那个数开始筛。

🦓题目细节：

🦓测试用例会给 L == 1，但是 1 既不是质数也不是合数，要特判，给 1 的话，要映射到 2.

🦓筛质数时，“合理倍数” 不能是 1 倍，那样就要筛去质数本身了。特判，最小倍数得是 2 倍。

#include<iostream> #include<cmath> using namespace std; typedef long long LL; const int N = 1e6 + 10; int l, r; bool st[N]; int p[N], cnt; bool ret[N]; void get_prime() { int n = sqrt(r); for (int i = 2; i <= n; i++) { if (!st[i]) p[++cnt] = i; for (int j = 1; 1ll * i * p[j] <= n; j++) { st[i * p[j]] = true; if (i % p[j] == 0) break; } } } int main() { cin >> l >> r; // 细节 1 l = l == 1 ? 2 : l; get_prime(); for (int i = 1; i <= cnt; i++) { LL x = p[i]; // 细节 2 for (LL j = max((l + x - 1) / x * x, 2 * x); j <= r; j += x) { ret[j - l] = true; } } int sum = 0; for (int i = l; i <= r; i++) { if (!ret[i - l]) sum++; } cout << sum << endl; return 0; }

OJ题来源：洛谷

OJ题名：Goldbach's Conjecture （哥德巴赫猜想）

OJ题归属：数学-数论【筛质数】

解题算法：线性筛

🐻算法原理：

🐻先用线性筛筛出题目指定范围的质数；

🐻两个质数差值最大，就是遍历 p数组 从小质数到大质数遍历，第一个符合题目条件的就是两个差值最大的质数，如何判断，n - a = b，看看 b 这个质数有没有被标记上，没有就是质数，st[n - a] = false。

#include<iostream> #include<cstring> using namespace std; typedef long long LL; const int N = 1e6 + 10; int n; bool st[N]; int p[N], cnt; // 预处理出质数 void get_prime() { for (LL i = 2; i <= 1e6; i++) { if (!st[i]) p[++cnt] = i; for (LL j = 1; i * p[j] <= 1e6; j++) { st[i * p[j]] = true; if (i % p[j] == 0) break; } } } int main() { get_prime(); while (cin >> n, n != 0) { bool flag = false; int x = 0, y = 0; for (int i = 2; i <= cnt; i++) { int a = p[i], b = -1; if (st[n - a] == false) // 关键特判 { flag = true; b = n - a; x = a, y = b; break; } } if (flag == false) cout << "Goldbach's conjecture is wrong." << endl; else cout << n << " = " << x << " + " << y << endl; } return 0; }