読者です 読者をやめる 読者になる 読者になる

素数を求めるアルゴリズム -エラトステネスの篩(ふるい)-

algorithm python

呼称: エラトステネスの篩(ふるい)
目的: 素数を求める
特徴: enumerate() を使うと便利です

アルゴリズムそのものとは全然関係ないのですが、お仕事でエラトステネスさんに由来する名前に関わっているので、実装してみました(^ ^;;

アルゴリズムの解説を Python で実装しているのをよく見かけるようになりました。id:naoya さんがブログで紹介しているアルゴリズムだったり、以下のような書籍だったりします。

集合知プログラミング

集合知プログラミング

私も wikipedia に記載されているステップ通りに実装していて、アルゴリズムそのものに注力してすっきり書けるなと実感しました。アルゴリズムの勉強に Python を使うと、実装におけるプログラミングの勘所を意識しないで良いかもしれません。

#!/usr/bin/env python                                   

import sys

def main():
    prime  = []
    search = range(2, int(sys.argv[1]))

    while not prime or prime[-1] ** 2 < search[-1]:
        hurui(search, prime)
    print prime + search

def hurui(s, p):
    p.append(s.pop(0))
    for i, num in enumerate(s):
        if num % p[-1] == 0:
            s.pop(i)

if __name__ == '__main__':
    main()

実行結果。

$ python eratosthenes.py 20
[2, 3, 5, 7, 11, 13, 17, 19]

キミならどう書く 2.0 - ROUND 1 - — Lightweight Language Ringで発見したのですが、この実装と同じ考えで、ワンライナを書くと以下になります。Python 凄いなと思ってしまいました。

>>> [p for p in range(2,20) if 0 not in [p%d for d in range(2,p)]]
[2, 3, 5, 7, 11, 13, 17, 19]

リファレンス:
wikipedia:エラトステネスの篩
素朴にエラトステネスのふるい (1) | すぐに忘れる脳みそのためのメモ
素朴にエラトステネスのふるい (2) - オブジェクト指向を手がかりに再帰表現を考える | すぐに忘れる脳みそのためのメモ
素朴にエラトステネスのふるい (3) – Python の実装を Haskell へ | すぐに忘れる脳みそのためのメモ