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

呼称: エラトステネスの篩(ふるい)
目的: 素数を求める
特徴: 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]

2017-01-17 追記

私の勘違いのようです。ごめんなさい。。。

@t2y エラトステネスのふるいのアルゴリズムはちゃんと実装すると計算量がO(nloglogn)-timeのようですが，記事で紹介しているワンライナーは計算量がO(n^2)-timeなので，違うアルゴリズムだと思います．

— knottyknot (@knottyknot) 2017年1月17日

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