2013-03-12

「アルゴリズムを、はじめよう」エラトステネスのふるいをPythonで書く

指定した数までの範囲の素数を一覧で表示させる問題。素数とは、2以上の整数の中で1とその数字自身以外では割り切れない数のこと。

「エラトステネスのふるい」っていうのは、ある数以下の範囲に存在する素数を探したい場合に、その数の平方根より小さい素数の倍数を全て消せば素数が残るという考え方です。

アルゴリズムを、はじめよう

第11章:エラトステネスのふるい(Sieve of Eratosthenes)のアルゴリズム


#!/usr/bin/env python
#-*- coding: utf-8 -*-
import sys, math

def eratosthenes(max):
    max += 1
    array = range(max)
    array[0] = array[1] = 0

    for m in xrange(2, int(math.sqrt(max))):
        for i in xrange(2, max):
            if m * i < max:
                array[m * i] = 0
    primeNumbers(array)

def primeNumbers(array):
    for e in array:
        if not e == 0:
            print e

if __name__ == '__main__':
    eratosthenes(max=100)

いろんな人が書いているのを参考にさせてもらったけど、何となくしっくりこなくて何とか自分で書いた。

かなりごちゃごちゃしてきた。これは改善しないといけない。

0 件のコメント:

コメントを投稿