我们知道一般的素数判断是\(O(\sqrt{n})\)的复杂度的,当\(n \le 10^{14}\)且仅判断个数较少的情况下尚且能用,如果需要判断k个较大的数字(\(n \le 10^{18}\))的数字,估计一下要运算\(k * 10^8\)之多,显然无法接受。 介绍 / Introduction 这里介绍的MillerRabin算法是一种可以在\(O(k*log^{2}{2})\)的复杂度内 […]
我们知道一般的素数判断是\(O(\sqrt{n})\)的复杂度的,当\(n \le 10^{14}\)且仅判断个数较少的情况下尚且能用,如果需要判断k个较大的数字(\(n \le 10^{18}\))的数字,估计一下要运算\(k * 10^8\)之多,显然无法接受。 介绍 / Introduction 这里介绍的MillerRabin算法是一种可以在\(O(k*log^{2}{2})\)的复杂度内 […]
Eriktse
18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。
COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.
Theme Kratos | Hosted In TENCENT CLOUD