38 lines
1.4 KiB
C++
38 lines
1.4 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
// 欧拉筛
|
|||
|
|
const int N = 1e6 + 10;
|
|||
|
|
int primes[N], cnt; // primes[]存储所有素数
|
|||
|
|
bool st[N]; // st[x]存储x是否被筛掉
|
|||
|
|
void get_primes(int n) {
|
|||
|
|
for (int i = 2; i <= n; i++) {
|
|||
|
|
if (!st[i]) primes[cnt++] = i;
|
|||
|
|
for (int j = 0; primes[j] * i <= n; j++) {
|
|||
|
|
st[primes[j] * i] = true;
|
|||
|
|
if (i % primes[j] == 0) break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
// 加快读入
|
|||
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|||
|
|
// 欧拉筛求出区间内所有质数
|
|||
|
|
get_primes(N - 1); // 不能到N，因为数组下标从0开始！要不会越界~
|
|||
|
|
|
|||
|
|
int n;
|
|||
|
|
|
|||
|
|
while (cin >> n, n) {
|
|||
|
|
for (int i = 1;; i++) { // 枚举每个奇数质数,不用上界，因为认为哥德巴赫猜想是正确的，肯定有解
|
|||
|
|
int a = primes[i]; // primes[0]=2,因为2特殊，是质数，并且是奇数，本题要求是奇数，放过数字2
|
|||
|
|
int b = n - a; // 差值
|
|||
|
|
if (!st[b]) { // 差值也是质数,这个st数组用的漂亮啊，我还以为要在primes中二分呢
|
|||
|
|
// 第一个找的就是最小奇数质数因子，所以相对就是最大的奇数质数因子，两者的差就是最大
|
|||
|
|
printf("%d = %d + %d\n", n, a, b);
|
|||
|
|
break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return 0;
|
|||
|
|
}
|