P1579哥德巴赫猜想

寫來自己學習用~

題目內容：

1742年6月7日哥德巴赫寫信給當時的大數學家歐拉，正式提出了以下的猜想：任何一個大于9的奇數都可以表示成3個質數之和。質數是指除了1和本身之外沒有其他約數的數，如2和11都是質數，而6不是質數，因為6除了約數1和6之外還有約數2和3。需要特別說明的是1不是質數。

現在請你編一個程序驗證哥德巴赫猜想。

先給出一個奇數n，要求輸出3個質數，這3個質數之和等于輸入的奇數。

輸入格式：

僅有一行，包含一個正奇數n，其中9<n<20000

輸出格式：

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

方法：

在入門題目里面，所以首先覺得暴力應該能過，但是有兩組數據超時了。

于是想到之前做的求一百億以內的素數那道題（最初一直在用篩法），所以在做這道題是就先根據素數的倍數一定不是素數，對n以內所有非素數進行標記，在后面的程序中就不需要用函數判斷是否是素數了。

之后就直接做就可以了。

?