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

前回のエントリで書いたスクリプトには、LLRing ブログのコメントにあった美しいスクリプトにも、欠点がある。 それは N が大きくなるとメモリ消費量が膨大に増えてしまうこと。

原因は最初に 2 から N までの自然数を全て含む集合を作ってしまうことにある。

range(2, N )

この部分だね。このほかにも、結果を全て含むリストを作成してからそれを返しているのもメモリを大量に消費してしまう原因だ。これを解消したスクリプトを作ってみた。

def search_prime( max ):
    probable_prime = 2
    prime = None
    
    while probable_prime <= max :
        aNum = 2
        while aNum < probable_prime :
            if (probable_prime % aNum) == 0 :
                break
            elif( probable_prime % aNum ) != 0 :
                if aNum == ( probable_prime -1 ) :
                    prime = probable_prime
                    yield prime
        
            aNum += 1
        
        probable_prime += 1


if __name__ == "__main__" :
    import sys
    for i in search_prime( int(sys.argv[1]) ):
        print i,

このコードはエラトステネスの篩ではなくて、素数の定義そのものをもとに書きました。つまり、「素数とは、1とその数自身以外に正の約数を持たない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のことである」（Wikipedia「素数」より引用)です。言い換えると、1より大きな自然数 i について、i を 2以上 i 未満の自然数で割ったときの余りが全て 0 でなければ自然数 i は素数なのです。

2以上 N 以下の 任意の自然数 i 全てについて、上記の定義が当てはまるものを探しています。そして、当てはまるものが見つかったらそれを即座に yield しています。

この方法でメモリ消費量は抑えられたのですが、今度は処理速度が・・・ orz

Relative

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

re: 君ならどう書く 2.0 -Round3-