如何评估质数判断算法的运行时间？

本文共计1379个文字，预计阅读时间需要6分钟。

测试标准+这里使用两种、五种常用质数判断算法：枚举子法（暴力、开方优化、6n再优化）、质数筛（埃氏筛法、欧拉筛法）。（Miller-Rabin？不会，没搞懂）+ 同时，使用质数筛。

测试标准

这里使用两类、五种常用质数判断算法进行测试：枚举因子法（暴力、开方优化、6n再优化）、质数筛（埃氏筛法、欧拉筛法）。（Miller-Rabin呢？不会，没搞懂）

同时，使用两类情况进行测试：

1. 寻找 2-100,000 内的质数个数
2. 寻找 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\le\sqrt{n}\)。因此，只需要判断 [2-\(\sqrt n\)]之间的数即可。