题解 P1579 【哥德巴赫猜想（升级版）】

IOCTYCNconbill · 2018-08-06 22:44:46 · 题解

//翻看了一下各位大犇的代码，好像没有和我一样的，鼓起勇气发一篇题解//代码有点短。

这个题目求任意一个大于九的奇数等于三个质数的和，题目说明了第一个质数要最小，其次第二个，据此可以进行优化循环的次数。然后就是进入正题了 ,首先先要明白一件事，三个数相加为奇数，只有两种可能

①两个偶数加一个奇数.

②三个奇数.

①先判断前两个质数都是偶数的情况，因为偶数中只有2是素数，那么就只要判断这个（n-4）是否为素数，如果是，就直接输出2,2，n-4。

②如果这三个数都是质数，那么从i=3开始循环，并保证i为奇数并且i为素数，再在第二重循环里面让j=i并保证j为奇数且j为素数，最后只要判断（n-i-j)是否为奇数且为素数就行了，满足就输出答案。

#include<bits/stdc++.h>
using namespace std;
int check(int x){
    for (int i=2;i*i<=x;i++)
    if(x%i==0) return 0;
    return 1;
}
int main(){
    int n;
    cin>>n;
    if(check(n-4)) {
    cout<<"2 "<<"2 "<<n-4;
    return 0;
    }     //第一种情况
    for (int i=3;i<n;i++)//第二种情况
    if((i%2)!=0&&check(i))//优化
    for (int j=i;j<n;j++)
        if((j%2)!=0&&check(j))//优化
        if(check(n-i-j)) {
        cout<<i<<" "<<j<<" "<<n-i-j;return 0;//不用循环第三个数，优化。
        }

}