[問題] 請教問題如何將時間縮短 timmy999 PTT批踢踢實業坊

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

作者: timmy999 (憤怒a阿宅) 2019-05-04 21:32:10

題目: 輸入一數字判斷它是否為 prime , not prime
或是emirp(若71為質數 17也是質數則71和17為emirp)
我的程式碼:https://ideone.com/VVsKxB
這題個位數質數和11不算emirp
我覺得我的code沒什麼問題但是會一直出現time limit exceed
希望能幫我看看是哪邊可以縮短謝謝

作者: nh60211as 2019-05-04 21:59:00

不太熟，不過檢查質數不用檢查到N-1，你可以上網看看檢查質數的方法

作者: allensheng (上將帽子) 2019-05-04 22:00:00

找質數的地方就爆了下面就沒看了

作者: CCWck (幹嘛要暱稱) 2019-05-05 00:15:00

質數先用篩法建表，第一次加入2、3、5、7建出10以下的質數表，再用來建立100一下的質數表，再建立10000一下的質數表。差不多就夠用建表之後，你只要判斷題目給的數字是否在表裡面就好進入 while scanf之後 re=0沒有重新清掉，不確定是否會有問題若re變很大下面判斷emirp的for就會跑很久

作者: firejox (Tangent) 2019-05-05 11:55:00

用個miller rabin也很快

作者: eye5002003 (下一夜) 2019-05-05 13:01:00

miller一票

作者: hichcock (快樂一整年 ^^~~~) 2019-05-06 09:44:00

miller time 快又有效

作者: xavier13540 (柊四千) 2019-05-06 10:43:00

推miller rabin 缺點是只能驗到32-bit integer 除非用部分compiler內建的128-bit integer

作者: cutekid (可愛小孩子) 2019-05-06 14:38:00

https://bit.ly/2VL6g3r

作者: eye5002003 (下一夜) 2019-05-08 15:41:00

miller跟32bit限制無關,找個GMP之類的工具來用就好

作者: xavier13540 (柊四千) 2019-05-09 11:50:00

演算法本身跟大小無關但實作上關係可大了啊@@

多個Log就可以處理64-bit integer了

繼續閱讀

[問題] ShellCode中, String後面帶Null的問題mikemagic88 [問題] 使用openwrt製作7688Duo的ipk檔wert880032 [問題] 想釐清指標(pointer)與參考(reference)ptter0619 [問題] QT button跟connect的問題Mysterydog [問題] 3n+1 problemOri185 [問題] C++的Unicode字串被C#呼叫使用Stevenashh [問題] 請教一題pointer的問題mazz [問題] 一個專案多個WinExec/systemjayzhuang [問題] Makefile問題Hack [問題] 想請教為什麼會變無限迴圈z820413z

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

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