月度归档: 2023年3月

2 篇文章

thumbnail
素数的判断算法比较
素数的判断算法比较 参与对比的几个素数判断算法: 朴素算法 朴素算法的平方优化 Miller-Rabin 素性测试 埃筛 线性筛 判断单个素数的时间复杂度 $O(n)$ $O(\sqrt{n})$ $O(k;log^3;n)$ ($k$为进行$k$轮检测) $O(n;log;log;n)$ $O(n)$ 对于朴素算法以及素性测试,判断单个素数用时较…