- 1LeetCode 114. 二叉树展开为链表（一题三吃）
- 2探针配置失误，线上容器应用异常死锁后，kubernetes集群未及时响应自愈重启容器？_应用节点加上探针后为什么频繁重启
- 3网络安全-自学笔记_网络安全学习
- 4mysqldump参数 --master-data详解_mysqldump --master-data
- 5win10系统安装docker （2022年最新填坑）_win10安装docker
- 6Java-Spark系列1-spark概述_java spark
- 7Python跨年烟花秀_python跨年代码
- 8windows版 docker desktop学习笔记——2 容器仓库管理_docker desktop创建命名空间
- 9《成为一名优秀的架构师：从基础到实践》_现代c++软件架构:方法与实践 pdf
- 10大家都在用的AI作画Python几行代码就可实现_python人工智能代码
C++质数判断算法的时间测试_c++判断质数最小时间复杂度
赞
踩
测试标准
这里使用两类、五种常用质数判断算法进行测试：枚举因子法（暴力、开方优化、6n再优化）、质数筛（埃氏筛法、欧拉筛法）。（Miller-Rabin呢？不会，没搞懂）
同时，使用两类情况进行测试：
- 寻找 2-100,000 内的质数个数
- 寻找 10,000,001-10,009,999 内的质数个数
质数判断算法
枚举因子法
1. 暴力遍历
很显然，判断n是不是质数，最简单的只要暴力从2到n过一遍就可以了
template <class IntT> bool isPrime(IntT n) { | |
if (n <= 1) | |
return false; | |
for (IntT i=2; i<n; i++) { | |
if (n % i == 0) | |
return false; | |
} | |
return true; | |
} |
分析：最坏情况（是质数）每个都遍历一遍，时间复杂度O(n)，平均情况由于质数分布也是O(n)
2. 开方优化
容易推出，若一个数n不是质数，则它必然有一个因数F≤n。因此，只需要判断 [2-n]之间的数即可。
template <class IntT> bool isPrime(IntT n) { | |
if (n <= 1) | |
return false; | |
for (IntT i=2; i*i<=n; i++) { | |
if (n % i == 0) | |
return false; | |
} | |
return true; | |
} |
分析：时间复杂度降为O(n)
3. 6n优化
再想一想就会发现，我们对于2、3的倍数做了太多次重复运算：一个数模2不等于0，那么它模4、6、8也都不会等于0；3也一样。这些重复在6次的周期内会重复4次。因此，我们可以考虑优化它们，即：
除特殊情况外，只需考虑因数为6n−1和6n+1的情况（n为正整数）
template<class IntT> bool isPrime(IntT n) { | |
if (n <= 1) | |
return false; | |
if (n <= 5 && n != 4) | |
return true; | |
if (n % 2 == 0 || n % 3 == 0) | |
return false; | |
for (IntT i=5; i*i<=n; i+=6) { | |
if (n % i == 0 || n % (i + 2) == 0) | |
return false; | |
} | |
return true; | |
} |
分析：虽然时间复杂度没降，但速度显著提升了
筛法
这里就不详细讲解了，主要是运用已知的质数遍历，减少求范围内质数时重复的遍历次数（筛法都会更耗空间）。
1. 埃氏筛法
（注：这里加了个小小的优化，在第二层循环里，j初始化为i*i）
template<class IntT> IntT get_primes_num(IntT n) { | |
if (n <= 1) | |
return 0; | |
bool *isPrimes = new bool[n + 1]; | |
IntT *primes = new IntT[n - 1], | |
pn = 0; | |
memset(isPrimes, 1, n - 1); | |
for (IntT i=2; i<=n; i++) { | |
if (isPrimes[i]) { | |
primes[pn++] = i; | |
for (IntT j=i*i; j<=n; j+=i) | |
isPrimes[j] = false; | |
} | |
} | |
delete isPrimes; | |
delete primes; | |
return pn; | |
} |
时间复杂度为O(nlnlnn)（这一堆原理自己搜去，我自己也讲不清楚）
2. 欧拉筛法
对于埃氏筛法的进一步优化
template<class IntT> IntT get_primes_num(IntT n) { | |
if (n <= 1) | |
return 0; | |
bool *isPrimes = new bool[n + 1]; | |
IntT *primes = new IntT[n - 1], | |
pn = 0; | |
memset(isPrimes, 1, n - 1); | |
for (IntT i=2; i<=n; i++) { | |
if (isPrimes[i]) | |
primes[pn++] = i; | |
for (IntT j=0; i*primes[j]<=n; j++) { | |
isPrimes[i * primes[j]] = false; | |
if (i % primes[j] == 0) | |
break; | |
} | |
} | |
delete isPrimes; | |
delete primes; | |
return pn; | |
} |
时间复杂度为O(n)。注意：在n不大的时候，欧拉筛法与埃氏筛法比并不具有绝对优势，还有可能被反超（毕竟只是优化了个lnlnn），几乎相当于拼常数
测试
好了，接下来就是我们的核心——测试环节了。我这里在本机使用了一个基于std::chrono的封装计时库（程序主体部分运行至少6s）。记录以微秒（μs，百万分之一秒）为单位。
（windows x64 AMDRyzen5-5600H）
回顾一下两种情况：
- 寻找 2-100,000 内的质数个数
- 寻找 10,000,001-10,009,999 内的质数个数
（筛法：你故意找茬是吧）
| 平均用时(μs) | 情况1 | 情况2 |
|---|---|---|
| 暴力遍历 | 647,400 | 8,800,000 |
| 平方优化 | 3,985 | 3,496 |
| 6n优化 | 1,363 | 1,163 |
| 埃氏筛 | 154.5 | 35,000 |
| 欧拉筛 | 265.5 | 50,000 |
总结
平时做算法题的时候，如果说是从1或者一个较小的数开始计数的，那么建议使用埃氏筛（欧拉筛实现起来更烦，还不一定拼得过加了优化的埃式筛法（ps：优化加了容易数据容易溢出，建议用unsigned long long），要么去掉优化老老实实用j=2i）；
反之，如果是都在一个较高位的，那么建议使用6n优化，容易写，比平方优化效率也高很多。这时候再使用两次筛法的差值，时间就容易爆掉（就算一次也容易爆时间）。
好了，以上就是本人对C++质数判断算法的时间测试的所有内容了，初次创作，如有错误欢迎指出ヾ(^▽^*)))
