C++素数查找代码中的计数器使用及相关优化问题

初始疑问回复 #

• 问题1：C++是否存在for all类型的语言构造？
  C++标准库提供了对应的语义实现，<algorithm>头文件中的std::all_of、std::any_of、std::none_of算法可以直接实现"所有元素满足条件/任意元素满足条件/所有元素都不满足条件"的遍历判断逻辑，不需要手写计数器。比如你要判断一个数n是否无法被所有已存素数整除，可以直接写：

  bool is_prime = std::none_of(primes.begin(), primes.end(), [n](int p) { return n % p == 0; });
  

• 问题2：计数器变量的写法是否不推荐？
  确实不推荐。首先你用double类型存储计数器属于类型误用，用int即可；其次额外维护计数器的逻辑冗余，可读性差，也容易引入逻辑bug。更简洁的方案要么用上述标准库算法，要么参考你优化版的思路：找到能整除的素数就直接返回非素数的结果，不需要维护额外计数变量。
• 问题3：更高效率的素数查找方案？
  你当前用的试除法时间复杂度较高，不适合10亿量级的计算：
  1. 试除法本身还可以优化：判断素数时不需要遍历所有已存素数，只需要遍历到不大于√n的素数即可，因为如果n存在大于√n的因子，对应的另一个因子必然小于√n，早就被检测过了。
  2. 找固定范围内的素数优先用筛法：埃拉托斯特尼筛法（埃氏筛）时间复杂度为O(n log log n)，远优于试除法，适合1亿以内的素数查找；如果需要更高效率或者1亿以上的范围，可以用线性筛（欧拉筛），时间复杂度为O(n)，还可以附带计算多种数论函数；10亿量级可以用区间筛法拆分范围计算，避免内存占用过大的问题。

补充问题回复（break对耗时无影响的原因） #

你写的break属于永远不会执行的死代码：return false语句执行后会直接退出is_prime函数，后面的break根本没有运行的机会，编译器编译阶段就会把这段无效代码优化掉，所以加不加对运行耗时都没有影响，这段break可以直接删除。

另外补充一个优化点：你当前的is_prime函数遍历了所有已存素数，加上primes[p] * primes[p] <= n的判断条件，可以大幅减少循环次数，提升大数字的素数判断效率。

内容的提问来源于stack exchange，提问作者twj