[問題] 判斷質數 執行逾時
線上高中生解題系統 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
推
12/19 19:04, , 1F
12/19 19:04, 1F
我的質數表：
int p[]={2,3,5,7,11,13..............四千多個}
然後跳出程式碼太長，無法執行。
還是可以fopen("質數表.txt")？
※ 編輯: noodleT 來自: 140.117.196.151 (12/19 19:07)
→
12/19 19:06, , 2F
12/19 19:06, 2F
→
12/19 19:07, , 3F
12/19 19:07, 3F
→
12/19 19:13, , 4F
12/19 19:13, 4F
→
12/19 20:44, , 5F
12/19 20:44, 5F
→
12/19 21:01, , 6F
12/19 21:01, 6F
※ 編輯: noodleT 來自: 140.117.196.151 (12/19 21:40)
推
12/19 21:59, , 7F
12/19 21:59, 7F
→
12/19 22:13, , 8F
12/19 22:13, 8F
推
12/19 23:10, , 9F
12/19 23:10, 9F
→
12/19 23:47, , 10F
12/19 23:47, 10F
→
12/20 00:03, , 11F
12/20 00:03, 11F
→
12/20 00:04, , 12F
12/20 00:04, 12F
推
12/20 00:14, , 13F
12/20 00:14, 13F
→
12/20 00:17, , 14F
12/20 00:17, 14F
推
12/20 00:17, , 15F
12/20 00:17, 15F
→
12/20 00:19, , 16F
12/20 00:19, 16F
http://ideone.com/Lu5l3K
DEV C++ 和 ideone 的網站可以過，測驗系統卻出現分段記憶體錯誤ˊ ˋ
※ 編輯: noodleT 來自: 140.117.196.151 (12/20 00:54)
推
12/20 01:41, , 17F
12/20 01:41, 17F
→
12/20 01:41, , 18F
12/20 01:41, 18F
→
12/20 01:42, , 19F
12/20 01:42, 19F
推
12/20 02:11, , 20F
12/20 02:11, 20F
推
12/20 02:14, , 21F
12/20 02:14, 21F
→
12/20 11:49, , 22F
12/20 11:49, 22F