PTT數位生活區 / C_and_CPP (C/C++)

[問題] 請教問題 如何將時間縮短

看板C_and_CPP (C/C++)作者 (憤怒a阿宅)時間6年前 (2019/05/04 21:32), 6年前編輯推噓9(9推 0噓 10→)
留言19則, 9人參與, 6年前最新討論串1/1
題目: 輸入一數字 判斷它是否為 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
→
05/04 21:59, 6年前 , 1F
不太熟，不過檢查質數不用檢查到N-1，你可以上網看看
05/04 21:59, 1F
→
05/04 21:59, 6年前 , 2F
檢查質數的方法
05/04 21:59, 2F
推
05/04 22:00, 6年前 , 3F
找質數的地方就爆了 下面就沒看了
05/04 22:00, 3F
了解了 謝謝 ※ 編輯: timmy999 (59.127.63.20), 05/04/2019 22:29:29
推
05/05 00:15, 6年前 , 4F
質數先用篩法建表，第一次加入2、3、5、7建出10以下的質數
05/05 00:15, 4F
→
05/05 00:15, 6年前 , 5F
表，再用來建立100一下的質數表，再建立10000一下的質數表
05/05 00:15, 5F
→
05/05 00:15, 6年前 , 6F
。差不多就夠用
05/05 00:15, 6F
→
05/05 00:16, 6年前 , 7F
建表之後，你只要判斷題目給的數字是否在表裡面就好
05/05 00:16, 7F
推
05/05 00:33, 6年前 , 8F
進入 while scanf之後 re=0沒有重新清掉，不確定是否會有
05/05 00:33, 8F
→
05/05 00:33, 6年前 , 9F
問題
05/05 00:33, 9F
推
05/05 00:36, 6年前 , 10F
若re變很大下面判斷emirp的for就會跑很久
05/05 00:36, 10F
有我注意到re了 還沒學過建表 等等google 感謝 ※ 編輯: timmy999 (36.238.64.211), 05/05/2019 01:07:25
→
05/05 11:55, 6年前 , 11F
用個miller rabin也很快
05/05 11:55, 11F
推
05/05 13:01, 6年前 , 12F
miller一票
05/05 13:01, 12F
→
05/06 09:44, 6年前 , 13F
miller time 快又有效
05/06 09:44, 13F
推
05/06 10:43, 6年前 , 14F
推miller rabin 缺點是只能驗到32-bit integer 除非
05/06 10:43, 14F
→
05/06 10:43, 6年前 , 15F
用部分compiler內建的128-bit integer
05/06 10:43, 15F
推
05/06 14:38, 6年前 , 16F
05/06 14:38, 16F
→
05/08 15:41, 6年前 , 17F
miller跟32bit限制無關,找個GMP之類的工具來用就好
05/08 15:41, 17F
推
05/09 11:50, 6年前 , 18F
演算法本身跟大小無關但實作上關係可大了啊@@
05/09 11:50, 18F
推
05/11 23:42, 6年前 , 19F
多個Log就可以處理64-bit integer了
05/11 23:42, 19F
‣ 更多 timmy999 的文章
文章代碼(AID): #1SpPHWN7 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 timmy999 的文章
文章代碼(AID): #1SpPHWN7 (C_and_CPP)