エラトステネスの篩

先日の記事にも書きました任天堂のCode Puzzleを解いた際、結果的には使わなかったのですが試行錯誤の仮定でエラトステネスの篩を書いたので更新頻度の低さをごまかすために載せときます(^_^;)

def eratos_sieve(max_num=NUM):
    prime = [True] * max_num
    prime[0] = prime[1] = False
    prime_numbers = []
    for i in xrange(max_num):
        if prime[i]:
            j = 2
            while i * j < max_num:
                prime[i * j] = False
                j += 1

    for j, n in enumerate(prime):
        if n:
            prime_numbers.append(j)

    return prime_numbers

if __name__ == '__main__':
    for v in eratos_sieve():
        print v

    print u'end'

この書き方ですと最初にmax_num個分のリストを作成するためかなりメモリが必要で速度も遅いのですが、アルゴリズムを愚直に実装した形になっているのではないかと思います。