題目描述
輸入一個(gè)偶數(shù) N N N，驗(yàn)證 4 ～ N 4\sim N 4～N 所有偶數(shù)是否符合哥德巴赫猜想：任一大于 2 2 2 的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)之和。如果一個(gè)數(shù)不止一種分法，則輸出第一個(gè)加數(shù)相比其他分法最小的方案。例如 10 10 10， 10 = 3 + 7 = 5 + 5 10=3+7=5+5 10=3+7=5+5，則 10 = 5 + 5 10=5+5 10=5+5 是錯(cuò)誤答案。
輸入格式
第一行輸入一個(gè)正偶數(shù) N N N
輸出格式
輸出 N ? 2 2 \dfrac{N-2}{2} 2N?2? 行。對于第 i i i 行：
首先先輸出正偶數(shù) 2 i + 2 2i+2 2i+2，然后輸出等號，再輸出加和為 2 i + 2 2i+2 2i+2 且第一個(gè)加數(shù)最小的兩個(gè)質(zhì)數(shù)，以加號隔開。
樣例 #1
樣例輸入 #1
10
樣例輸出 #1
4=2+2
6=3+3
8=3+5
10=3+7
提示
數(shù)據(jù)保證，$ 4 \leq N\leq10000$。
1.題目分析
輸入一個(gè)偶數(shù)，代表右邊界，從4到有邊界遍歷每一個(gè)偶數(shù)，輸出每一個(gè)偶數(shù)的兩個(gè)質(zhì)數(shù)之和，保證左邊的質(zhì)數(shù)最小化。
說一下質(zhì)數(shù)的判斷方法：不能夠被1以外的任何自身的因子整除。文章來源：http://www.zghlxwxcb.cn/news/detail-638773.html
2.題目思路
寫一個(gè)判斷質(zhì)數(shù)的函數(shù)，輸入N，寫一個(gè)數(shù)組存儲(chǔ)N以內(nèi)的所有質(zhì)數(shù)，
用一個(gè)三層循環(huán)，第一層代表4到N的偶數(shù)，第二層代表第一個(gè)質(zhì)數(shù)的遍歷，第三層代表第二個(gè)質(zhì)數(shù)的遍歷，
然后判斷偶數(shù)等于兩個(gè)質(zhì)數(shù)之和的情況，打印即可。
值得一提的是，第一個(gè)質(zhì)數(shù)應(yīng)該小于第二個(gè)質(zhì)數(shù)，
遍歷到一組和的時(shí)候，需要直接結(jié)束本輪最外部的偶數(shù)循環(huán)。文章來源地址http://www.zghlxwxcb.cn/news/detail-638773.html
3.代碼實(shí)現(xiàn)
#include <stdio.h>
#include <math.h>
//判斷質(zhì)數(shù)的函數(shù)
int isPrimer(int n) {
int flag = 1;
//對1和0進(jìn)行特判
if (n == 1 || n == 0) {
flag = 0;
}
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) {
//可以被自身整除則不為質(zhì)數(shù)
flag = 0;
}
}
return flag;
}
int main() {
int n;
scanf("%d", &n);
//存放n以內(nèi)所有的質(zhì)數(shù)
int arr[n];
int cnt = 0;
for (int j = 2; j < n; ++j) {
//存放質(zhì)數(shù)
if (isPrimer(j) == 1) {
arr[cnt] = j;
cnt++;
}
}
//跳出內(nèi)部循環(huán)的標(biāo)記
int flag = 1;
//遍歷偶數(shù)
for (int i = 4; i <= n; i += 2) {
for (int j = 0; j < cnt; ++j) {
flag = 1;
for (int k = j; k < cnt; ++k) {
//判斷質(zhì)數(shù)之和等于偶數(shù)
if (arr[j] + arr[k] == i) {
printf("%d=%d+%d\n", i, arr[j], arr[k]);
flag = 0;
}
}
//當(dāng)本輪偶數(shù)找到質(zhì)數(shù)和之時(shí)，跳出本輪
if (flag == 0) {
break;
}
}
}
return 0;
}
到了這里，關(guān)于P1304 哥德巴赫猜想的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
