hdu 2138 How many prime numbers

2

_____________________________
ACM STEPS里的…这题前面一道是求LCM….结果接下来就是这么一道。。。
朴素会超….筛法会爆….题目顺序真是按照难度来的?
于是想到 Miller-Rabin素数测试…….
这个方法是基于费马小定理
我的理解就是…
如果我要判断n是否为素数
只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。
证明什么的…暂时还是算了吧…论文里貌似扯了一大堆
第一次用,竟然真的A了。。。。
感觉更好的办法也许是先打一个比较小的素数表,然后每次random选取若干个进行判断…那样应该更可靠些?
本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水?

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz