指定した数までの範囲の素数を一覧で表示させる問題。素数とは、２以上の整数の中で１とその数字自身以外では割り切れない数のこと。
「エラトステネスのふるい」っていうのは、ある数以下の範囲に存在する素数を探したい場合に、その数の平方根より小さい素数の倍数を全て消せば素数が残るという考え方です。
第１１章：エラトステネスのふるい（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)
いろんな人が書いているのを参考にさせてもらったけど、何となくしっくりこなくて何とか自分で書いた。
かなりごちゃごちゃしてきた。これは改善しないといけない。