一个很偶然的机遇发现了这道数论题。
竟然抢到了 $ 1A $，挺激动的。毕竟第一次嘛。
废话不多说，看题。
题目不难理解，就是给你一个奇数，让你用至多 $ 3 $ 个质数的和来表示它。
数据范围是 $ 10^9 $，乍一看无法用暴力解决此题。
然而我们转念一想：
“ $ CF $ 的机子，emmm”
再仔细看了看，回忆回忆自己学习的数论知识，确定无法用 $ O(1) $ 等时间复杂度较低的方法了（如果有请私信我，评论我有可能看不到）。
然后再想：怎么打暴力？
“一个奇数”、“质数和”
“woc这不是哥德巴赫猜想嘛”
没错，就是哥德巴赫猜想。
把原数减去一个 $ 3 $ ，然后直接暴力求解就星了。
$ \rm code $
# include <bits/stdc++.h> inline void xhw(); using namespace std; inline bool is_prime(int); int n; int main() { xhw(); return 0; } void xhw() { scanf("%d", &n); if(n == 3) { puts("1"); puts("3"); return; } if(n == 5) { puts("1"); puts("5"); return; } if(n == 7) { puts("1"); puts("7"); return; }//先来一堆特判 puts("3"); printf("3 "); n -= 3; //将n减去3 for(register int i = 2; i < n - 1; i ++) if(is_prime(i) && is_prime(n - i)) { //直接用朴素判断素数算法跑暴力 printf("%d %d", i, n - i); return; } } inline bool is_prime(int x) { for(register int i = 2; i * i <= x; i ++) if(x % i == 0) return false; return true; }
原文：https://www.cnblogs.com/Xray-luogu/p/11006453.html