【水】关于判断质数

Deuteron @ 2022-02-10 11:16:57

by dhclientqwq @ 2022-02-10 11:19:54

O(1)

by Fatalis_Lights @ 2022-02-10 11:20:57

你是说 AKS 素性检测？

by lsj2009 @ 2022-02-10 11:21:04

@小可爱萌萌哒 T\log{n}，其中 T 是一个常数，T 值越大，判断成功率就越高（也就是说不能 100\% 的判断素数），当 T=10 时，判断成功率已高于 99.99\%。

by 一个简单名字 @ 2022-02-10 11:21:22

程序外打表，O(1) 查询（bushi

by Fatalis_Lights @ 2022-02-10 11:22:04

目前 OI 题里 Miller Rabin 的准确度应该够用了罢。

by TLEWA @ 2022-02-10 11:23:50

大家的判断质数程序都是怎样的?,你学我?

by Fatalis_Lights @ 2022-02-10 11:24:00

@lsj2009 我记得 MR 是 \Theta(\log^3{n}) 的

by Fatalis_Lights @ 2022-02-10 11:27:59

@TLEWA 为啥是 logn 的，这不是 sqrtn 吗。

by Rubidium_Chloride @ 2022-02-10 11:28:32

@TLEWA 为什么是 \log 的，能否解释，，我怎么看都只能看出来上届 是 \sqrt{n} 的……

by TLEWA @ 2022-02-10 11:28:35

@SSelrewop 打错了.......