python - Python：一种在给定范围内生成素数的紧凑方法

Question

最近我读到了一种非常简洁的方式来生成素数列表，在 Python

#'prime' should be a pre-defined upper bound of the range
filter(lambda prime:all(prime%num for num in range(2,prime)),range(2,prime))

什么是pros和cons来适应它来生成素数？它是 Pythonic 的吗？

我个人的想法是它有点可读且非常简化，我不确定这是否是一种好的编码方式，我不肯定代码是否有效

Answer 1

该代码执行78021prime = 10000次除法，而传统方法只需要 2302 次。

http://ideone.com/X0MhGO

您的方法可以通过仅检查奇数并停在 来改进sqrt(x)：

primes = [2] + filter(lambda p: all(p % n for n in range(3, int(sqrt(p)) + 1, 2)), range(3, max, 2))

这仍然比“传统”算法差，但比原来的算法好得多（2351 divs vs 78021）。

Answer 2

优点和缺点主要是算法而不是句法。这段代码使用一种简单的方法来生成这些素数，虽然您可以对其进行一些优化，但如果遇到性能问题，最好使用完善的算法。否则，这并不重要，尽管我个人会将上面的代码编写为生成器表达式：

(cand for cand in range(2,upper_limit) if all(cand%num for num in range(2,cand)))

（注意：你有两个不相关的变量都prime在你的原始代码中命名，所以我将它们重命名为我认为合适的）

Answer 3

有更好的方法，这个函数很慢，原因如下：

• 一个一个地经历，当你可以简化为两个两个时，因为除了两个之外的所有偶数都不是素数

• 此外，它一直循环到最终数字，当它永远不会超过它的平方根时

这是检查数字是否为素数的更好功能的示例。

如果您至少在寻找速度，那么这些是主要问题。

Answer 4

缺点：生成器将是更好的选择。我也发现它相当慢。

优点：它将所有素数放入一个列表中，我想这是一个优点。

这是我在素数周围使用的函数。