素数を列挙する

プログラミングの練習。指定された範囲にある素数を列挙するプログラムを作ってみる。

素数表を使った判定

利用するアルゴリズムは自明のもの。つまり、正整数 n に対して √ n を超えない素数で割り切れるかどうかをチェックしている。初回の実行では 2 (最小の素数)から始めて素数表を作っている。実行中に作った素数表は最後にファイルに書き出す。2 回目以降の実行では、以前に作った素数表を読み込んでいる。

列挙した素数の後にカッコ付きで表示する数字は計算回数だ。

	#!/opt/local/bin/ruby1.9 -w
	# -*- coding: utf-8 -*-
	# listprimes.rb: make a list of prime numbers.
	def die(*x)
	STDERR.puts x
	exit 1
	end
	if ARGV.length < 2
	die <<USAGE
	Usage: #{__FILE__} <start> <range>
	print prime numbers (start <= primes < start + range)
	USAGE
	end
	start = ARGV.shift.to_i
	range = ARGV.shift.to_i
	PRIMES_FILE = "primes.txt"
	$primes = []
	if File.exist?(PRIMES_FILE)
	File.foreach(PRIMES_FILE) do |line|
	$primes.push(line.to_i)
	end
	end
	$updated = false
	$primes = [2] if $primes.size < 1
	$max_prime = $primes[-1]
	def prime_check(n)
	c = 1
	limit = Math::sqrt(n)
	$primes.each do |p|
	break if p > limit
	return [false, c] if (n % p == 0)
	c += 1
	end
	[true, c]
	end
	($max_prime...start).each do |n|
	next if $primes.include?(n)
	if prime_check(n)[0]
	$primes.push(n)
	$updated = true
	end
	end
	$max_prime = $primes[-1] if $updated
	print "START (#{$max_prime}):\n"
	start = 2 if start < 2
	t0 = Time.now
	(start...(start + range)).each do |n|
	if n <= $max_prime
	if $primes.include?(n)
	print "#{n} (0)\n"
	end
	else
	is_prime, counter = prime_check(n)
	if is_prime
	$primes.push(n)
	$updated = true
	print "#{n} (#{counter})\n"
	end
	end
	end
	elapsed = Time.now - t0
	print "Elapsed: #{elapsed}\n"
	if $updated
	File.open(PRIMES_FILE, "w") do |of|
	$primes.each do |p|
	of.puts(p)
	end
	end
	end

view raw listprimes.rb hosted with ❤ by GitHub

検証

念には念を入れて、listprimes.rb で作られた primes.txt を検証する。以下がそのプログラムだ。素数を判定するアルゴリズムは大して変わっていない(素数表を使わず √ n 以下の整数で割り切れるか否かをチェック)から、どちらかと言えばプログラムのバグを確認するためのものというべきだ。

	#!/opt/local/bin/ruby1.9 -w
	# -*- coding: utf-8 -*-
	# checkprimes.rb: check each prime in primes.txt
	PRIMES_FILE = "primes.txt"
	$primes = []
	if File.exist?(PRIMES_FILE)
	File.foreach(PRIMES_FILE) do |line|
	$primes.push(line.to_i)
	end
	end
	def prime?(n)
	return true if n == 2
	return false if n.even?
	d = 3
	limit = Math::sqrt(n)
	while d <= limit
	return false if (n % d == 0)
	d += 2
	end
	true
	end
	$primes.each do |p|
	print "#{p} is not a prime number.\n" if ! prime?(p)
	end

view raw checkprimes.rb hosted with ❤ by GitHub

実行結果

[imac] mnbi% ls primes.txt
ls: primes.txt: No such file or directory
[imac] mnbi% ./listprimes.rb 1000 50
START (2):
1009 (12)
1013 (12)
1019 (12)
1021 (12)
1031 (12)
1033 (12)
1039 (12)
1049 (12)
Elapsed: 0.00011
[imac] mnbi% tail primes.txt
991
997
1009
1013
1019
1021
1031
1033
1039
1049
[imac] mnbi% ./listprimes.rb 1000 50
START (1049):
1009 (0)
1013 (0)
1019 (0)
1021 (0)
1031 (0)
1033 (0)
1039 (0)
1049 (0)
Elapsed: 0.000444

初回の listprimes.rb の実行で、primes.txt が作られ、2 回目の実行では、(素数判定のための)計算がされていないことが(計算回数の表示から)読み取れる。意外なことに計算のない 2 回目の方が時間がかかっている。

「√ n 以下の整数」を使うより「√ n 以下の素数」の方が計算回数がぐっと少なくなると考えて素数表を使うようにしたんだが、実際のところでは素数表(配列)の操作にかかる時間の方が律速段階になっているようだ。素数表を使う方法で 2 回目以降の実行(つまり割り算は一切ない)でも、Time で計測してもわかるほどの差が出る。

素数表の検索を工夫すれば逆転するだろうか？

関連リンク

• 素数 (Wikipedia:ja)