AcWing算法提高课 数学知识
筛质数
哥德巴赫猜想的内容如下：
任意一个大于 44 的偶数都可以拆成两个奇素数之和。
例如：
8=3+58=3+5
20=3+17=7+1320=3+17=7+13
42=5+37=11+31=13+29=19+2342=5+37=11+31=13+29=19+23现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。
输入格式
输入包含多组数据。
每组数据占一行，包含一个偶数 nn。
读入以 00 结束。
输出格式
对于每组数据，输出形如
n = a + b，其中 a,ba,b 是奇素数。若有多组满足条件的 a,ba,b，输出 b?ab?a 最大的一组。
若无解，输出
Goldbach‘s conjecture is wrong.。数据范围
6≤n<1066≤n<106
输入样例：
8 20 42 0输出样例：
8 = 3 + 5 20 = 3 + 17 42 = 5 + 37
线性筛
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n;
int p[N], cnt;
bool st[N];
void get_primes()
{
st[0] = st[1] = 1;
for (int i = 2; i <= N; i ++ )
{
if (!st[i]) p[cnt ++ ] = i;
for (int j = 0; i * p[j] <= N; j ++ )
{
st[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
}
int main()
{
get_primes();
while (cin >> n, n)
{
for (int i = 0; i < n; i ++ )
if (!st[i] && !st[n - i])
{
printf("%d = %d + %d\n", n, i, n - i);
break;
}
}
return 0;
}
题目：
夏洛克有了一个新女友（这太不像他了！）。
情人节到了，他想送给女友一些珠宝当做礼物。
他买了 nn 件珠宝，第 ii 件的价值是 i+1i+1，也就是说，珠宝的价值分别为 2,3,…,n+12,3,…,n+1。
华生挑战夏洛克，让他给这些珠宝染色，使得一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同。
并且，华生要求他使用的颜色数尽可能少。
请帮助夏洛克完成这个简单的任务。
输入格式
只有一行一个整数 nn，表示珠宝件数。
输出格式
第一行一个整数 kk，表示所使用的颜色数；
第二行 nn 个整数，表示第 11 到第 nn 件珠宝被染成的颜色。
若有多种答案，输出任意一种。
请用 11 到 kk 表示你用到的颜色。
数据范围
1≤n≤1051≤n≤105
输入样例1：
3输出样例1：
2 1 1 2输入样例2：
4输出样例2：
2 2 1 1 2
分析：
我们让素数是一种颜色，合数是另一种颜色
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
int p[N], cnt;
bool st[N];
void get_prime(int n)
{
st[0] = 1; st[1] = 1;
for (int i = 2; i <= n; i++ )
{
if (!st[i]) p[cnt ++ ] = i;
for (int j = 0; p[j] * i <= n; j ++ )
{
st[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
}
int main()
{
cin >> n;
get_prime(n + 1);
if (n > 3) cout << 2 << endl;
else cout << 1 << endl;
for (int i = 2; i <= n + 1; i ++ )
if (!st[i]) printf("%d ", 1);
else printf("%d ", 2);
}
题目：
给定两个整数 LL 和 UU，你需要在闭区间 [L,U][L,U] 内找到距离最接近的两个相邻质数 C1C1 和 C2C2（即 C2?C1C2?C1 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。
同时，你还需要找到距离最远的两个相邻质数 D1D1 和 D2D2（即 D1?D2D1?D2 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。
输入格式
每行输入两个整数 LL 和 UU，其中 LL 和 UU 的差值不会超过 106106。
输出格式
对于每个 LL 和 UU，输出一个结果，结果占一行。
结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）
如果 LL 和 UU 之间不存在质数对，则输出
There are no adjacent primes.。数据范围
1≤L<U≤231?11≤L<U≤231?1
输入样例：
2 17 14 17输出样例：
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
分析：
将L到R的合数筛出来，用st[i - L]表示
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int p[N], cnt;
bool st[N];
bool vis[N];
void init()
{
for (int i = 2; i <= N; i ++ )
{
if (!st[i]) p[cnt ++ ] = i;
for (int j = 0; p[j] * i <= N; j ++ )
{
st[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
}
int w[N];
int main()
{
init();
// for (int j = 0; j < cnt; j ++ ) cout << p[j] << " ";
// cout << endl;
int l, r;
while (cin >> l >> r)
{
memset(vis, 0, sizeof vis);
for (int i = 0; i < cnt; i ++ )
{
ll pp = p[i];
for (ll j = max(2 * pp, (l + pp - 1) / pp * pp); j <= r; j += pp )
vis[j - l] = true;
}
int tot = 0;
for (int i = 0; i <= r - l;i ++ )
if (!vis[i] && i + l >= 2)
w[tot ++ ] = i + l;
if (tot < 2) puts("There are no adjacent primes.");
else
{
int mi = 0, mx = 0;
for (int i = 0; i + 1 < tot; i ++ )
{
int d = w[i + 1] - w[i];
if (d < w[mi + 1] - w[mi]) mi = i;
if (d > w[mx + 1] - w[mx]) mx = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n", w[mi], w[mi + 1], w[mx], w[mx + 1]);
}
// for (int i = l; i <= r; i ++ )
// cout << vis[i - l] << " ";
// cout << endl;
// int start = l, last = l;
// int a = 2e9, b = -2e9;
// for (int i = l + 1; i <= r; i ++ )
// {
// if (!vis[i - l] && !vis[start - l] && a > i - start + 1)
// {
// a = i - start + 1;
// start = i;
// }
// if (!vis[i - l] && !vis[last - l] && b < i - last + 1)
// {
// b = i - last + 1;
// last = i;
// }
// }
// // cout << a << endl;
// if (a == 2e9) puts("There are no adjacent primes.");
// else printf("%d,%d are closest, %d,%d are most distant.\n", start - a + 1, start, last - b + 1, last);
}
}
原文：https://www.cnblogs.com/Iamcookieandyou/p/15046783.html