[問題] 判斷質數 執行逾時

[noodleT (麵T)]

線上高中生解題系統 a007:判斷質數
http://zerojudge.tw/ShowProblem?problemid=a007

Code:
http://ideone.com/HaHWTn


判斷流程:

先判斷是否為2、再判斷是否為偶數，

如果以上皆非，則判斷是否可以被 ≦sqrt(x) 的奇數整除。


這問題的重點應該是sqrt()吧？

我也有試過建立 ≦sqrt(2147483647) 的質數表，約有4600個質數，

但被打槍(程式碼太長)。

想請教大家是如何做這題的，有效利用『測資點 1 (100%): 2.0s, 512 MB』

的條件？

--

我是麵T，哩賀
http://ppt.cc/-eS5

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.117.196.151
推 x000032001:記得是預建一個質數表 讀進來以後用質數表去檢驗
我的質數表：

int p[]={2,3,5,7,11,13..............四千多個}

然後跳出程式碼太長，無法執行。

還是可以fopen("質數表.txt")？
※ 編輯: noodleT         來自: 140.117.196.151      (12/19 19:07)
→ x000032001:建1~2147483647的表好像也可以 只是要弄成＜512MB
→ Feis:檢驗法
→ noodleT:可以請稍微說明一下檢驗法嗎？
→ walelile:http://ppt.cc/dceD 這個?
→ ChampYen:你應該只檢測質數而非奇數...
※ 編輯: noodleT         來自: 140.117.196.151      (12/19 21:40)
推 lc85301:1-2147483647只要檢測4600次就好...
→ CCWck:用篩法建質數表比較快
推 EdisonX:這題我覺得篩法要寫好其實不算好寫說....
→ CCWck:篩完剛好符合題目就直接判斷是不是質數啦~
→ EdisonX:默默的自己玩了快一小時，篩法寫完我也 TLE 了 Orz
→ EdisonX:http://codepad.org/0oXSEE0V , 記體剛好512mb,不過太慢.
推 stimim:在讀 input 前把質數表(2~sqrt(2^31))建好就可以了
→ stimim:可以看 #1Gt3EK-o (C_and_CPP)
推 EdisonX:先謝謝 stimim，太晚了，明晚再繼續玩吧，謝謝。
→ EdisonX:奇怪，原來以前我用6n + sqrt 法則可以過，現在不能過 XD
http://ideone.com/Lu5l3K

DEV C++ 和 ideone 的網站可以過，測驗系統卻出現分段記憶體錯誤ˊ ˋ
※ 編輯: noodleT         來自: 140.117.196.151      (12/20 00:54)
推 s25g5d4:前幾天剛寫過 用 C 寫埃拉托斯特尼篩法 1.1 秒通過
→ s25g5d4:可是看到有人 0.3s 0.4s 就 AC 實在無法理解
→ s25g5d4:後來 FB 社團有人提 Miller-Rabin Algorithm 但是我看不懂
推 s25g5d4:http://ideone.com/MBHseh
推 EdisonX:就米勒拉賓質數測試，檢驗法的一種。
→ x000032001:是說他測資不知道幾行就是 說不定又是那種可以IO加速的