【洛谷】P1579 哥德巴赫猜想(升级版)

题目链接：P1579

#include<iostream>

#include<cmath>

using namespace std;

int IsPrime(int n);

int main()

{

    int number;
    int a,b;
    int flag=0;

    cin>>number;//输入奇数

    for(a=2;;a++)//寻找第一个数a
    {
        for(b=a;b<=number-a-b;b++)//寻找第二个数b
        {
            if( IsPrime(a) && IsPrime(b) && IsPrime(number-a-b) )//判断三个数是否都是质数
            {
                flag=1;
                cout<<a<<" "<<b<<" "<<number-a-b<<endl;//若都是质数，输出
                break;//终止内循环
            }
        }

        if(flag==1)	
			break;//终止外循环
    }

    return 0;
}

int IsPrime(int n)
{
 if(n<=1)
 {
  return 0;
 }
 if(n==2 || n==3) 
 {
  return 1;
 }
 if(n%6!=1 && n%6!=5) //不是6x两侧的数肯定不是素数
 {
  return 0;
 }
 for(int i=5;i<=(int)sqrt(n);i+=6) //对6x两侧的数进行判断
    if(n%i==0 || n%(i+2)==0) 
       return 0;
 return 1; 
}