エラトステネスの篩を実行するコード

eratosthenes.rb

maximum_number = 10000000

# 得られた素数を保管する配列
primes = []

# 素数の候補となる数の配列
numbers = (2..maximum_number).to_a

p = numbers.first

while p*p <= maximum_number

	# 素数の候補から先頭の数を取得する
	p    = numbers.first
	last = numbers.last

	# p は素数なので素数の配列に加える
	primes.push p

	# (p の倍数) の配列を作る
	multiples_of_p = []
	multiple = p
	while multiple <= last
		multiples_of_p.push multiple
		multiple += p
	end

	# 素数の候補から (p の倍数) を取り除く（篩にかける）
	numbers = numbers - multiples_of_p

end


# 残った素数候補を配列に追加
primes = primes + numbers


# 素数の配列を出力
p primes