作者timmy999 (憤怒a阿宅)
看板C_and_CPP
標題[問題] 請教問題 如何將時間縮短
時間Sat May 4 21:32:10 2019
題目: 輸入一數字 判斷它是否為 prime , not prime
或是emirp(若71為質數 17也是質數 則71和17為emirp)
我的程式碼:
https://ideone.com/VVsKxB
這題個位數質數和11不算emirp
我覺得我的code沒什麼問題 但是會一直出現time limit exceed
希望能幫我看看是哪邊可以縮短 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.127.63.20
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1556976736.A.5C7.html
1F：→ nh60211as: 不太熟，不過檢查質數不用檢查到N-1，你可以上網看看 05/04 21:59
2F：→ nh60211as: 檢查質數的方法 05/04 21:59
3F：推 allensheng: 找質數的地方就爆了 下面就沒看了 05/04 22:00
了解了 謝謝
※ 編輯: timmy999 (59.127.63.20), 05/04/2019 22:29:29
4F：推 CCWck: 質數先用篩法建表，第一次加入2、3、5、7建出10以下的質數 05/05 00:15
5F：→ CCWck: 表，再用來建立100一下的質數表，再建立10000一下的質數表 05/05 00:15
6F：→ CCWck: 。差不多就夠用 05/05 00:15
7F：→ CCWck: 建表之後，你只要判斷題目給的數字是否在表裡面就好 05/05 00:16
8F：推 CCWck: 進入 while scanf之後 re=0沒有重新清掉，不確定是否會有 05/05 00:33
9F：→ CCWck: 問題 05/05 00:33
10F：推 CCWck: 若re變很大下面判斷emirp的for就會跑很久 05/05 00:36
有我注意到re了 還沒學過建表 等等google 感謝
※ 編輯: timmy999 (36.238.64.211), 05/05/2019 01:07:25
11F：→ firejox: 用個miller rabin也很快 05/05 11:55
12F：推 eye5002003: miller一票 05/05 13:01
13F：→ hichcock: miller time 快又有效 05/06 09:44
14F：推 xavier13540: 推miller rabin 缺點是只能驗到32-bit integer 除非 05/06 10:43
15F：→ xavier13540: 用部分compiler內建的128-bit integer 05/06 10:43
17F：→ eye5002003: miller跟32bit限制無關,找個GMP之類的工具來用就好 05/08 15:41
18F：推 xavier13540: 演算法本身跟大小無關但實作上關係可大了啊@@ 05/09 11:50
19F：推 oToToT: 多個Log就可以處理64-bit integer了 05/11 23:42