空间方面最快的方法 - 用 python 查找素数 [英] Fastest-in term of space- way to find prime numbers with python

问题描述

也许这是一个愚蠢的问题，但我想知道您是否可以提供最短的源代码来使用 Python 查找素数.我还想知道如何使用 map() 或 filter() 函数查找素数.谢谢(:

Maybe it is a stupid question, but i was wondering if you could provide the shortest source to find prime numbers with Python. I was also wondering how to find prime numbers by using map() or filter() functions. Thank you (:

当我说最快/最短时，我指的是字符/单词较少的方式.无论如何，不​​要考虑竞争:我想知道是否有可能是单行源，而不删除总是用于循环的缩进.编辑 2:这个问题没有考虑到巨大的数字.我认为我们可以保持在一百万以下(范围(2,1000000)编辑 3:最短，但仍然优雅.正如我在第一个 EDIT 中所说的，您不需要将变量的名称减少为单个字母.我只需要一行，优雅的来源.谢谢！

When i say fastest/shortest I mean the way with the less characters/words. Do not consider a competition, anyway: i was wondering if it was possible a one line source, without removing indentation always used with for cycles. EDIT 2:The problem was not thought for huge numbers. I think we can stay under a million( range(2,1000000) EDIT 3: Shortest, but still elegant. As i said in the first EDIT, you don't need to reduce variables' names to single letters. I just need a one line, elegant source. Thank you!

推荐答案

埃拉托色尼筛网两行.

primes = set(range(2,1000000))
for n in [2]+range(3,1000000/2,2): primes -= set(range(2*n,1000000,n))

我已经意识到以上并不是真正的 Eratosthenes 筛选，因为它过滤的是奇数集而不是素数集，因此它不必要地变慢.我已经在接下来的版本中修复了这个问题，并且还包含了一些评论中指出的常见优化.

I've realized that the above is not a true Sieve of Eratosthenes because it filters on the set of odd numbers rather than the set of primes, making it unnecessarily slow. I've fixed that in the following version, and also included a number of common optimizations as pointed out in the comments.

primes = set([2] + range(3, 1000000, 2))
for n in range(3, int(1000000**0.5)+1, 2): primes -= set(range(n*n,1000000,2*n) if n in primes else [])

第一个版本仍然较短，并且确实生成了正确的结果，即使需要更长的时间.

The first version is still shorter and does generate the proper result, even if it takes longer.

这篇关于空间方面最快的方法 - 用 python 查找素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！