题目描述
输入一个不小于6的正整数n,将其拆分成三个素数之和,输出任意一解即可。
输入
输入存在多组测试数据,每组测试数据输入一行包含一个正整数n(6<=n<=20000)
输出
对于每组测试数据,输出三个素数,以空格分隔,行末无空格。
样例输入 Copy
6
7
8
样例输出 Copy
2 2 2
2 2 3
2 3 3
来源/分类
基础题 枚举
在做这道时得需要对哥德巴赫猜想有一定的了解,从而对题目进行一定的变形,
要不然就得超时。
今日常见的猜想陈述为欧拉的版本,即任一大于2的偶数都可写成两个素数之和,亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。
从关于偶数的哥德巴赫猜想,可推出:任何一个大于7的奇数都能被表示成三个奇质数的和。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。
先对输入数据为偶数的进行处理:
对输入数据减去二,剩下的值依然是个偶数,然后再通过暴力把剩下的两个素数求出来;
当输入数据为奇数时:
对输入数据减去3,剩下的值便是偶数,仍是通过暴力把剩下的两个素数求出来;
以上的输入数据均是大于等于6
#include<iostream>
using namespace std;
int isprime(int cnum);
int main()
{
int num;
while(cin>>num)
{
if(num%2==0)
{
cout<<2<<" ";
for(int i=2;i<num-2;i++)
{
if(isprime(i)&&isprime(num-2-i))
{
cout<<i<<" "<<num-2-i<<endl;
break;
}
}
}
else
{
for(int i=2;i<num-3;i++)
{
if(isprime(i)&&isprime(num-3-i))
{
cout<<i<<" "<<3<<" "<<num-3-i<<endl;
break ;
}
}
}
}
return 0;
}
int isprime(int cnum)
{
for(int i=2;i*i<=cnum;i++)
{
if(cnum%i==0)
return 0;
}
return 1;
}