エラトステネスのふるいのように見えますが、そうではありません。実際にはもっと悪いです。Sieve は、素数を見つけるための最適なアルゴリズムです。
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenesを参照してください。
編集: https://stackoverflow.com/a/9302299/711085をワンライナーに変更しました (元々は本物のふるいではありませんでしたが、現在は...おそらく...):
reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r),
range(2,N), set(range(2,N)))
デモ：
>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}
悲しいことに、これは関数型プログラミング言語では効率的ですが、非永続的な (共有状態で不変の) データ構造のため、Python ではそれほど効率的ではない可能性があり、Python のふるいは突然変異を使用して達成する必要があると思います同等の性能。どうしてもやりたい場合は、ワンライナーに詰め込むことができます。でもまず...
通常ふるい：
>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
... if table[i]:
... for mult in range(i**2,N,i):
... table[mult] = False
...
>>> primes = [p for p in table if p][1:]
>>> primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
同じ行で無名関数を定義して呼び出すことができるようになりました[...].__setitem__。また、インライン ミューテーションを実行するためのハックと、戻りながら... and foo評価するためのハックもできます。...foo
>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
恐怖に身を縮めると、ワンライナーが展開されます（制御フローをほぼ直接変換できるため、奇妙に美しいですが、すべてのひどい悪用です）：
lambda N:
(lambda table:
[[table.__setitem__(mult,False) for mult in range(i**2,N,i)]
for i in range(2,int(N**0.5)+1) if table[i]]
and [p for p in table if p][1:]
)(list(range(N)))
このワンライナーの変更バージョンは、私のマシンでは約 10 8で放棄されましたが、元の変更バージョンは約 10 9で放棄され、メモリが不足しました (奇妙なことに)。
元のバージョンは 10 7reduceであきらめました。したがって、おそらくそれほど効率が悪いわけではありません(少なくとも、コンピューターで処理できる数値については)。
edit2 次のように、副作用をより簡潔に悪用できるようです。
reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
if (x in r) else r),
range(2,N), set(range(2,N)))
10 8付近であきらめます。これは、ワンライナー変異バージョンと同じです。
edit3:これはO(N)経験的複雑さdifference_updateで実行されが、それがなければO(n^2.2) 複雑さで実行されます。
削減される範囲を上限の sqrt に制限し、オッズのみで作業すると、どちらも追加のスピードアップをもたらします (対応する2 倍と1.6倍):
reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
if (x in r) else r),
range(3, int((N+1)**0.5+1), 2),
set([2] + range(3,N,2)))