« [Python / LLRing ] re:君ならどう書く2.0 -Round 3- | トップページ | [ Python/LLRing] re: 君ならどう書く 2.0 -Round 1- 改 »

2006/08/26

[ Python/LLRing] re: 君ならどう書く 2.0 -Round 1-

お題は「100までの整数の中から素数を列挙する」こと。
素数を見つける方法といえばエラトステネスの篩。

primes = []

# Obviously 0 and 1 are not prime.
# This problem is equal that searching primes in a range( 2, 100+1 ).
set_of_int = range( 2, 100 + 1 )
dflag = {}
for d in set_of_int :
    dflag[d] = None

while( len( set_of_int ) ):
    # At the sieve, the top element of the list is always prime.
    # All integers included set_of_range[1: ] are devided by prime.
    # when a remainder is 0, the integer is not prime.
    for pp in set_of_int[1: ]:
        if( pp % set_of_int[0] ) == 0 :
            dflag[ pp ] = False

    for key in dflag.keys():
        if dflag[ key ] == False :
            dflag.pop( key )

    # remove the element that is identified as prime
    dflag.pop( set_of_int[0] )

    # append a prime to prime progression
    primes.append( set_of_int.pop(0) )

    # update probable prime
    set_of_int = dflag.keys()
print primes

めちゃめちゃ醜いです。美しさのかけらもありません orz
コメントを読まないと、たぶん何をやっているかさっぱりわからなくなるでしょう。

実は元エントリのコメントに素晴らしいコードがあるんですよ。残念なことにランキング投票の対象にはならなかったようですが、わたしはこのコードに一票入れたかったです。とても美しいコードです。

[p for p in range(2,100) if 0 not in [p%d for d in range(2,p)]]

最初に 2以上 100未満の整数の集合をつくり、その中の数 p に対して 2以上 p 未満の数で割ったあまりの集合を求めています。余りの集合の中に 0 がひとつでもあれば、割り切れる数があったということを意味しますからその数は素数ではないということになります。最終的に得られるリストは 2以上 p 未満の数では割り切れない数、つまり素数だけを集めたものになります。

リスト内包表記が使われたコードは「うわ、読みたくないなこれ」というような可読性がとても低いものが多いように思えます。しかし、このコードは実に簡単に理解できます。この点でも驚きました。素晴らしいです。

Relative
re: 君ならどう書く 2.0 -Round 1- 改
re: 君ならどう書く 2.0 -Round 3-

|

« [Python / LLRing ] re:君ならどう書く2.0 -Round 3- | トップページ | [ Python/LLRing] re: 君ならどう書く 2.0 -Round 1- 改 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/103108/11621340

この記事へのトラックバック一覧です: [ Python/LLRing] re: 君ならどう書く 2.0 -Round 1-:

« [Python / LLRing ] re:君ならどう書く2.0 -Round 3- | トップページ | [ Python/LLRing] re: 君ならどう書く 2.0 -Round 1- 改 »