[UVa] 10311 - Goldbach and Euler
網址
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呢…