素数判定的一些提问【数论吧】

03月26日漏签0天

数论吧关注：14,134贴子：81,277

4回复贴，共1页

<返回数论吧

素数判定的一些提问

只看楼主收藏回复

现在的素数判定比较好用的方法有哪些？我目前已知的最快的是对自然数n，开平方的取整m，判断2到m能否整除n，有更快的方法吗？

送TA礼物

IP属地:湖南

来自Android客户端1楼2025-03-11 10:45回复

如果有2到m的素数表, 就只要检验2到m中的素数能否整除n, 找出1~n所有的素数会比单独检验1~n中每个数是否为素数要快
另外还有用费马小定理, 欧拉准则, 卢卡斯数列这些素数相关的性质来快速检验的方法, 但都存在将合数认定为素数的可能, 这样的伪素数所占比例很少, 这类素性检验方法都是概率性检验

IP属地:北京

来自Android客户端2楼2025-03-11 11:46

收起回复