エラトステネスの篩
先日の記事にも書きました任天堂の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個分のリストを作成するためかなりメモリが必要で速度も遅いのですが、アルゴリズムを愚直に実装した形になっているのではないかと思います。