返回小于M的所有素数

Question

给定整数M.返回小于M的所有素数.

给出尽可能好的算法.需要考虑时间和空间的复杂性.

Answer 1

Eratosthenes的Sieve是一个很好的起点.

还有其他易于理解且不需要O(n)空间的筛子.或者你只是为了一遍又一遍的数量来做这件事.例如.你想要10000以下的所有素数,然后分批100或1000,以减少空间使用,然后只保存素数. (2认同)

Answer 2

一些额外的性能提示:

好吧,你不应该放弃所有这些!你不应该放弃2 ;-) (11认同)
我不确定你想说什么.当然可能有(无关)素数大于*N*的平方根,但这并没有告诉我们任何有用的东西.关键是每个复合数至少有一个素因子小于或等于其平方根,你只需要找到一个这样的因子来证明*N*是复合的(即不需要继续检查).这是第一个声明的重点. (4认同)
我认为第一个陈述是错误的.例如,N = 120. 113是素数<N,但是113> sqrt(N). (3认同)