[问题] 请教问题如何将时间缩短 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

[问题] 请教问题 如何将时间缩短

[问题] 请教问题如何将时间缩短