欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1081: 哥德巴赫猜想

程序员文章站 2022-07-15 10:38:59
...

题目描述
输入一个不小于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;
}
相关标签: 枚举类