当前位置：技术文章 > 编程面试题 >

返回所有小于M的质数

问题内容：

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

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

问题答案：

另外一些性能提示：

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