题解：P1304 哥德巴赫猜想

· · 题解

洛谷 P1304 题解

这题纯枚举呀！

解题思路

正常人写 for 循环都是这么办的吧。

for(int i=1;i<=n;i++){

}

由此我们可以发现 i 的变化是递增的。\ 题目也刚好说了最小的第一个加数。\ 那不就极其像 i 从小到大的变换过程了吗？

正式分析

哥德巴赫猜想：任意一个 \geqslant 4 的正整数都可以分解成由两个质数相加的和。\ 输入格式：输入一个 n，满足 10000 \geqslant n \geqslant 4。\ 输出格式：从 4 开始，每一个偶数的分解形式。\ 够清楚了吧！反正也没人看我题解。

实现过程

用质数筛，不懂的看我这篇题解。或者在洛谷循环结构里找，里面有的。\ 好的，来解决哥德巴赫的吧！\ 主体思路：用上面讲的循环来搞，如果 i 和 n - i 均为质数的话直接按照要求输出。\ 代码：

void gdbh(long long a1){
    for(int i=2;i<=a1;i++){
        if(zs(i)==1){
            if(zs(a1-i)==1){
                cout<<a1<<"="<<i<<"+"<<a1-i;
                return;
            }
        }
    }
}

主函数：从 i = 4 开始，每次循环 i + 2 。并执行 gdbh 函数。\ 代码：

int main(){
    long long a1;
    cin>>a1;
    for(long long i=4;i<=a1;i+=2){
        gdbh(i);
        cout<<endl;
    }
    return 0;
}

到这里还不会的点个赞再私信我哈。

Code

#include<iostream>
#include<algorithm>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
int a[1029][1029],b[1029][1029];
long zs(long long a2){
    for(int i=2;i<a2;i++){
        if(a2%i==0){
            return 0;
        }
    }
    return 1;
}
void gdbh(long long a1){
    for(int i=2;i<=a1;i++){
        if(zs(i)==1){
            if(zs(a1-i)==1){
                cout<<a1<<"="<<i<<"+"<<a1-i;
                return;
            }
        }
    }
}
int main(){
    long long a1;
    cin>>a1;
    for(long long i=4;i<=a1;i+=2){
        gdbh(i);
        cout<<endl;
    }
    return 0;
}

有优化的直接在评论里指出，我会及时回复的。