題目背景

1742年6月7日哥德巴赫寫信給當(dāng)時(shí)的大數(shù)學(xué)家歐拉，正式提出了以下的猜想：任何一個(gè)大于9的奇數(shù)都可以表示成3個(gè)質(zhì)數(shù)之和。質(zhì)數(shù)是指除了1和本身之外沒有其他約數(shù)的數(shù)，如2和11都是質(zhì)數(shù)，而6不是質(zhì)數(shù)，因?yàn)?除了約數(shù)1和6之外還有約數(shù)2和3。需要特別說明的是1不是質(zhì)數(shù)。

這就是哥德巴赫猜想。歐拉在回信中說，他相信這個(gè)猜想是正確的，但他不能證明。

從此，這道數(shù)學(xué)難題引起了幾乎所有數(shù)學(xué)家的注意。哥德巴赫猜想由此成為數(shù)學(xué)皇冠上一顆可望不可及的“明珠”。

題目描述

現(xiàn)在請你編一個(gè)程序驗(yàn)證哥德巴赫猜想。

先給出一個(gè)奇數(shù)n，要求輸出3個(gè)質(zhì)數(shù)，這3個(gè)質(zhì)數(shù)之和等于輸入的奇數(shù)。

輸入輸出格式

輸入格式：

僅有一行，包含一個(gè)正奇數(shù)n，其中9<n<20000

輸出格式：

僅有一行，輸出3個(gè)質(zhì)數(shù)，這3個(gè)質(zhì)數(shù)之和等于輸入的奇數(shù)。相鄰兩個(gè)質(zhì)數(shù)之間用一個(gè)空格隔開，最后一個(gè)質(zhì)數(shù)后面沒有空格。如果表示方法不唯一，請輸出第一個(gè)質(zhì)數(shù)最小的方案，如果第一個(gè)質(zhì)數(shù)最小的方案不唯一，請輸出第一個(gè)質(zhì)數(shù)最小的同時(shí)，第二個(gè)質(zhì)數(shù)最小的方案。

輸入輸出樣例

輸入樣例#1：?

2009

輸出樣例#1：?

3 3 2003

源代碼

#include<iostream> #include<cmath> using namespace std; bool prime(int n)//判斷是否是質(zhì)數(shù)的函數(shù) {int i;if(n==2) return true;if(n%2==0) return false;for(i=3;i<=sqrt(n);i+=2)if(n%i==0)return false;return true; } int main() {int number;int a,b;int flag=0;cin>>number;//輸入奇數(shù)for(a=2;;a++)//尋找第一個(gè)數(shù)a{for(b=a;b<=number-a-b;b++)//尋找第二個(gè)數(shù)b{if( prime(a) && prime(b) && prime(number-a-b) )//判斷三個(gè)數(shù)是否都是質(zhì)數(shù){flag=1;cout<<a<<" "<<b<<" "<<number-a-b<<endl;//若都是質(zhì)數(shù)，輸出break;//終止內(nèi)循環(huán)}}if(flag==1) break;//終止外循環(huán)}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的哥德巴赫猜想（升级版）（洛谷-P1579）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。