返回所有小于M的质数 [英] Return all prime numbers smaller than M

问题描述

给出一个整数M。返回所有小于M的素数。

Given an integer M. return all prime numbers smaller than M.

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

Give a algorithm as good as you can. Need to consider time and space complexity.

推荐答案

另外两个性能提示：

1. 您只需要测试 M 的平方根，因为每个复合数字的至少一个素数小于或等于其平方根


2. 您可以在生成已知质数时对其进行缓存，并仅针对此列表中的数字测试后续数字（而不是低于 sqrt的每个数字） （M））


3. 您显然可以跳过偶数（当然， 2 除外）

1. You only need to test up to the square root of M, since every composite number has at least one prime factor less than or equal to its square root
2. You can cache known primes as you generate them and test subsequent numbers against only the numbers in this list (instead of every number below sqrt(M))
3. You can obviously skip even numbers (except for 2, of course)

这篇关于返回所有小于M的质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！