エラトステネスの篩

エラトステネスの篩（エラトステネスのふるい）は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

(エラトステネスの篩 - Wikipedia より引用)

import math, sys
m = 100 + 1
if len(sys.argv) > 1: m = int(sys.argv[1])+1
n = range(2,m)
for i in range(2,int(math.sqrt(m))+1):
  for j in [x for x in range(i+1,m) if x % i < 1 and x in n]:
    n.remove(j)

print n

$ python eratosthenes.py [自然数]

を実行してやれば、2から[自然数]までの素数を列挙してくれる。
Python らしくリスト内包表記を使う。いいね、すっきりしている。