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

先做题自己思考再看解析呦~OJ题来源洛谷OJ题名素数密度OJ题归属数学-数论【筛质数】解题算法线性筛、埃氏筛算法原理借助素数的判定中用试除法从 [1sqrt r] 进行试除的原理在筛质数里面我们可以用 [1sqrt r] 中的质数去筛掉 [lr] 里面的合数。在对区间 [lr] 进行筛质数时要合理映射下标~筛质数时我们要从质数的 “合理倍数” 那个数开始筛。题目细节测试用例会给 L 1但是 1 既不是质数也不是合数要特判给 1 的话要映射到 2.筛质数时“合理倍数” 不能是 1 倍那样就要筛去质数本身了。特判最小倍数得是 2 倍。#includeiostream #includecmath 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题名Goldbachs Conjecture 哥德巴赫猜想OJ题归属数学-数论【筛质数】解题算法线性筛算法原理先用线性筛筛出题目指定范围的质数两个质数差值最大就是遍历 p数组 从小质数到大质数遍历第一个符合题目条件的就是两个差值最大的质数如何判断n - a b看看 b 这个质数有没有被标记上没有就是质数st[n - a] false。#includeiostream #includecstring 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 Goldbachs conjecture is wrong. endl; else cout n x y endl; } return 0; }