素数 - OI Wiki - Githubissues

Ir1d commented 6 years ago

https://oi-wiki.org/math/prime/

Phemon commented 5 years ago

CF 27E的代码无法通过该题 WA on No.8.

Ir1d commented 5 years ago

@Phemon 谢谢提醒，爆 int 了。。在 https://github.com/24OI/OI-wiki/pull/1251 中修复

growvv commented 5 years ago

341并不是卡迈克尔数，第一个卡迈克尔数是561

Ir1d commented 5 years ago

@growvv 谢谢提醒，稍后修复

sshwy commented 5 years ago

Miller-Rabin的复杂度是log^3的吗。。是log的吧

GreyTigerOIer commented 4 years ago

求因子数一定的最小数那里的temp / p[depth]是不是可以改成temp

YOYO-UIAT commented 4 years ago

@GreyTigerOIer 求因子数一定的最小数那里的temp / p[depth]是不是可以改成temp

temp记录的是数值

ZhongZijun01 commented 4 years ago

好像缺少了 Pollard-rho 算法的讲解啊

xtlsoft commented 4 years ago

@ZhongZijun01 好像缺少了 Pollard-rho 算法的讲解啊

有单独的章节讲解了。

leevanleevan commented 3 years ago

@YOYO-UIAT

@GreyTigerOIer 求因子数一定的最小数那里的temp / p[depth]是不是可以改成temp

temp记录的是数值

应该是ans/p[depth]<temp 就break吧？

Alpacabla commented 3 years ago

这里Miller-Rabin素性测试里的实现部分的可知其一定不是 p^e 的 p^e 是啥啊

ryomahan commented 3 years ago

Miller Rabin 算法中第二个 for 循环里为什么只判断 if (v == n - 1) break; 而不是 if (v == n - 1 || v == 1) break;

cyh-toby commented 3 years ago

Miller-Rabin 最后应该是循环 b - 1 次而非 b 次吧，以及之后判断也要微调一下？否则会放过去不满足费马小定理的数哇？

cyh-toby commented 3 years ago

@ryomahan Miller Rabin 算法中第二个 for 循环里为什么只判断 if (v == n - 1) break; 而不是 if (v == n - 1 || v == 1) break;

在进循环之前先判了是否等于 1，进循环说明最开始不可能等于 1。根据费马小定理，如果 n 是质数，最后一定会等于 1。而若 n 是质数，根据二次探测定理，平方等于 1 的 v 只能等于 1 或者 -1，如果 v 等于 1，那么 v 的平方根只能是 1 或 -1，递归下去，必然是 -1（前面说了最开始不是 1）。如果如你所说加上 v==1 的话，可能出现 v != -1 或 1，但是 v^2 = 1，显然 n 就不是质数，但你会判成质数。