網址

http://uva.onlinejudge.org/external/103/10311.html

題目概述

給你一個數N，問你是否可以由兩個質數相加所構成

Technique details

• 給定數字 N，0 < N ≤ 100000000
• Memory Limit: 40 MB
• Time Limit: 40 seconds (UVa瀏覽頁面卻是寫10.000 seconds 囧)

輸入格式

每行一筆測資，包含一個數字N，讀到EOF截止

輸出格式

針對每一個N，如果不能用兩個質數相加所構成則輸出:

N is not the sum of two primes!

否則則輸出:

N is the sum of p1 and p2.

其中p1跟p2為兩個質數

請確保(p2-p1)為正數且最小

解題思路

題目說p2-p1要是正數，

代表這兩個質數必為相異，且p1<p2

由於受限於Memory Limit

不能直接開1億大小的bool陣列進行篩法

(因為1億Bytes = 95.367 MB)

所以考慮區間篩法:

我們知道，一個數 N 要能夠判斷其是不是質數

必要檢查小於等於根號N 的所有質數

1億開根號 = 10000

所以只要有小於1萬的所有質數，

就可以知道1億以內的數是不是質數；

於是分區段進行篩法

每一百萬篩一次，並且記錄該一百萬個數中所有的質數到一個陣列prime

進行100次 (100*1000000=1億)

經過計算可以得到5761455個質數

接著分析兩個case:

如果N是奇數，奇數=偶數+奇數

所以如果要達成兩數都是質數，勢必偶數為2

只要檢查N-2是否也是質數就好；

如果N是偶數，則從N/2往下開始

找小於等於該數的最大質數K(Binary Search)

一樣Binary Search找出N-K是否也是質數

如此不斷往下找下一個質數

直到找到為止

這樣算出來得結果大概1.4x秒可以完成

*小心1不是質數，即便題目中有提到，但那也只是“conjecture” (猜測)

註:

經過測試，開一億的陣列可以過…

不過一樣使用Binary Search的結果卻是5.x秒

題目說好的Memory Limit呢…