测试标准
同时，使用两类情况进行测试：
质数判断算法
很显然，判断n是不是质数，最简单的只要暴力从2到n过一遍就可以了
template bool isPrime(IntT n) {
if (n
分析：最坏情况（是质数）每个都遍历一遍，时间复杂度(O(n))，平均情况由于质数分布也是(O(n))
容易推出，若一个数n不是质数，则它必然有一个因数(F\le\sqrt{n})。因此，只需要判断 [2-(\sqrt n)]之间的数即可。
template bool isPrime(IntT n) {
if (n
分析：时间复杂度降为(O(\sqrt n))
再想一想就会发现，我们对于2、3的倍数做了太多次重复运算：一个数模2不等于0，那么它模4、6、8也都不会等于0；3也一样。这些重复在6次的周期内会重复4次。因此，我们可以考虑优化它们，即：
除特殊情况外，只需考虑因数为(6n-1)和(6n+1)的情况（n为正整数）
template bool isPrime(IntT n) {
if (n
分析：虽然时间复杂度没降，但速度显著提升了
这里就不详细讲解了，主要是运用已知的质数遍历，减少求范围内质数时重复的遍历次数（筛法都会更耗空间）。
（注：这里加了个小小的优化，在第二层循环里，j初始化为 i*i）
template IntT get_primes_num(IntT n) {
if (n
时间复杂度为(O(n\ln\ln n))（这一堆原理自己搜去，我自己也讲不清楚）
对于埃氏筛法的进一步优化
template IntT get_primes_num(IntT n) {
if (n
时间复杂度为(O(n))。注意：在n不大的时候，欧拉筛法与埃氏筛法比并不具有绝对优势，还有可能被反超（毕竟只是优化了个(\ln\ln n)），几乎相当于拼常数
好了，接下来就是我们的核心——测试环节了。我这里在本机使用了一个基于 std::chrono的封装计时库（程序主体部分运行至少6s）。记录以微秒（μs，百万分之一秒）为单位。
（windows x64 AMDRyzen5-5600H）
回顾一下两种情况：
平均用时(μ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++质数判断算法的时间测试的所有内容了，初次创作，如有错误欢迎指出ヾ(^▽^*)))
Original: https://www.cnblogs.com/cup11/p/16441262.html
Author: cup11
Title: C++质数判断算法的时间测试
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713433/
转载文章受原作者版权保护。转载请注明原作者出处！