› 看板 C_and_CPP 關於我們 聯絡資訊
作者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://www.ptt.cc/bbs/C_and_CPP/M.1556976736.A.5C7.html
→ nh60211as: 不太熟，不過檢查質數不用檢查到N-1，你可以上網看看 05/04 21:59
→ nh60211as: 檢查質數的方法 05/04 21:59
推 allensheng: 找質數的地方就爆了 下面就沒看了 05/04 22:00
了解了 謝謝 ※ 編輯: timmy999 (59.127.63.20), 05/04/2019 22:29:29
推 CCWck: 質數先用篩法建表，第一次加入2、3、5、7建出10以下的質數 05/05 00:15
→ CCWck: 表，再用來建立100一下的質數表，再建立10000一下的質數表 05/05 00:15
→ CCWck: 。差不多就夠用 05/05 00:15
→ CCWck: 建表之後，你只要判斷題目給的數字是否在表裡面就好 05/05 00:16
推 CCWck: 進入 while scanf之後 re=0沒有重新清掉，不確定是否會有 05/05 00:33
→ CCWck: 問題 05/05 00:33
推 CCWck: 若re變很大下面判斷emirp的for就會跑很久 05/05 00:36
有我注意到re了 還沒學過建表 等等google 感謝 ※ 編輯: timmy999 (36.238.64.211), 05/05/2019 01:07:25
→ firejox: 用個miller rabin也很快 05/05 11:55
推 eye5002003: miller一票 05/05 13:01
→ hichcock: miller time 快又有效 05/06 09:44
推 xavier13540: 推miller rabin 缺點是只能驗到32-bit integer 除非 05/06 10:43
→ xavier13540: 用部分compiler內建的128-bit integer 05/06 10:43
推 cutekid: https://bit.ly/2VL6g3r 05/06 14:38
→ eye5002003: miller跟32bit限制無關,找個GMP之類的工具來用就好 05/08 15:41
推 xavier13540: 演算法本身跟大小無關但實作上關係可大了啊@@ 05/09 11:50
推 oToToT: 多個Log就可以處理64-bit integer了 05/11 23:42