1. 首页
  2. 问题
  3. 返回所有小于M的质数
一尘不染

返回所有小于M的质数

algorithm

给定整数M。返回所有小于M的质数。

尽力提供一种算法。需要考虑时间和空间的复杂性。


阅读 260

收藏
2020-07-28

共1个答案

一尘不染

另外一些性能提示：

  1. 您只需要测试的平方根M，因为每个复合数至少有一个素数小于或等于其平方根
  2. 您可以在生成已知质数时对其进行缓存，并仅针对此列表中的数字（而不是下面的每个数字sqrt(M)）测试后续数字。
  3. 您显然可以跳过偶数（2当然，除外）
2020-07-28