1081: 哥德巴赫猜想

题目描述
输入一个不小于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;
}
上一篇:SSH使用手机验证登陆


下一篇:char是所有类型中最短的 char多为8位,