Pythonで素数

素数を捜すのに、素数で割ってみる、っていうのが意外とむずかしいのかもしれない...
Pythonだとどうやるんだろ?

Wikipediaのエラトステネスの篩のgifを見てたら、このまんまできそうじゃね?と思い、やってみたメモ。
例?によってlambdaしばりで。

do = lambda *x : x
switch = lambda x : x[-1]


primes = (
  lambda n : find_primes( range( 2, n + 1 ), ( n + 1 ) ** 0.5, [ ] )
)

find_primes = (
  lambda xs, end_point, ys :

    switch(
      xs[0] <= end_point and do( ys.append( xs[0] )
                            , find_primes( remove_fst_multiples( xs ) , end_point, ys )
                            )

      or                    do( ys.extend( xs ) 
                            , ys 
                            )
    )
)

remove_fst_multiples = (
  lambda xs : [ x for x in xs if x % xs[0]  ]
)

print primes(100)

実行結果：

[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]

アルゴリズムはWikipediaのまんまです。

primesは、いい感じで値を渡すだけの関数。実体はfind_primes。

find_primesは、

• 探索リストと、終了条件値と素数リストを引数にして、
• 探索リストの先頭の数が終了条件値以下なら、
• 先頭値を素数リストに加え、
• 先頭値の倍数を除いた新しい探索リストと終了条件値と新しい素数リストで再帰的にfind_primesを呼ぶ。
• 探索リストの先頭値が終了条件値を超えたら、
• 残っている探索リストを素数リストに結合して、素数リストを返す。

remove_fst_multiplesは、リストをとって、そのリストの先頭値の倍数を除いたリストを返す。

itertoolsを使ってみる

コメントいただいたので使ってみました。
といっても、どういうものかわかってないのでググってみて、とりあえず探索リストをイテレータで置き換えてみた。
ちゃんとした使い方はコメントの方とか、他にもいろいろ発表されているのでそちらを見てください。

from itertools import count, ifilter, takewhile

do = lambda *x : x
switch = lambda x : x[-1]


primes = ( lambda n : 
  find_primes( 
    takewhile(lambda x : x < n + 1, count(2))
  , ( n + 1 ) ** 0.5
  , [ ] 
  )
)

find_primes = (
  lambda xs, end_point, ys :
    (lambda a = next( xs ) :

      switch(
       a <= end_point and do( ys.append( a )
                        , find_primes( remove_multiples( xs, a ) , end_point, ys )
                        )

        or              do( ys.append( a )
                        , ys.extend(list( xs) ) 
                        , ys 
                        )
      )
    )()
)

remove_multiples = (
  lambda xs, a : ifilter(lambda x : x % a , xs )
)

print primes(100)