我今天闲来无事,用 Scala 实现了一个粗糙但是正确的 Miller–Rabin素性测试算法。
跑了一下,你给出的这两个数都是素数。用时 ~200 毫秒。
出错概率 < 4^(-100) ~= 10^(-60)
可以认为就是素数了。
【 在 feng321 的大作中提到: 】
: 标 题: 如何快速准确的判断一个73位(甚至207位)的数,是不是素数?
: 发信站: 水木社区 (Thu Mar 14 16:31:32 2024), 站内
:
: 无意间,产生一个73位的数,网站说是素数。我如何快速准确的判断是不是素数呢?
: 2171215253114636109376559870215896869956324375013957926424893086146552813
: 还有,比如
: 544060619151779046651409439300707217946129505352004115332837604713312178459013241836215088519140362769108316187482548035828239378680817620486605476208245611699136004275024704575687750493252005005477334848117
: 这个207位的,网站也说是素数。我如何快速准确的判断出来?
: --
: ※ 修改:·feng321 于 Mar 14 16:34:14 2024 修改本文·[FROM: 120.242.238.*]
: ※ 来源:·水木社区
http://www.mysmth.net·[FROM: 120.242.238.*]
--
修改:feng321 FROM 120.242.238.*
FROM 14.112.12.*