素数を列挙する #2

前回の続き。

素数表の検索にバイナリサーチを使う

前回、素数の判定法としてはもっとも素直な「√n 以下の整数で割る」よりは割り算が少なくなると考え、素数表を使った「√n 以下の素数で割る」方法を実装してみた。ところが、列挙範囲の素数表が完成している場合であっても(つまり割り算は一度も行わない)、「√n 以下の整数で割る」方が速いという結果になった。

その原因は Array#include? を使った素数表の検索にあるのではないかと考え、今回は検索に「バイナリサーチ(二分検索)」を使ってみることにした。

(listprimes_binsearch.rb より)
def ($primes).binsearch(n)
  len = self.size
  first = 0
  last = len - 1
  while len > 0
    mid = first + len / 2
    v = self[mid]
    if n == v
      return true
    elsif n < v
      last = mid - 1
    else
      first = mid + 1
    end
    len = last - first + 1
  end
  false
end

結果として、Array#include? を使ったものより高速になったことはもちろん、(素数表が完成していれば)列挙する範囲によっては「√n 以下の整数で割る」ものよりも速くなった。とはいえ、やはり素数表を生成しながらの場合は、比較にならないほど遅い。

• listprimes_binsearch.rb

エラトステネスの篩

素数表の生成でもう少し速そうな方法を試してみることにした。有名な「エラトステネスの篩」だ。コードを以下に示す。

	#!/opt/local/bin/ruby1.9 -w
	# -*- coding: utf-8 -*-
	# listprimes_sieve.rb: make a list of prime numbers using the sieve of Eratosthenes
	start = ARGV.shift.to_i
	start = 2 if start < 2
	range = ARGV.shift.to_i
	def sieve(start, range)
	limit = start + range
	max = Math::sqrt(limit).to_i
	s = Array.new(limit, true)
	s[0] = s[1] = false
	i = step = 2
	while i <= max
	j = i + step
	while j < limit
	s[j] = false
	j += step
	end
	i += 1
	until s[i] or i > max
	i += 1
	end
	step = i
	end
	primes = []
	(start...limit).each do |n|
	primes.push(n) if s[n]
	end
	return primes
	end
	t0 = Time.now
	sieve(start, range).each do |p|
	print "#{p}\n"
	end
	elapsed = Time.now - t0
	print "Elapsed: #{elapsed}\n"

view raw listprimes_sieve.rb hosted with ❤ by GitHub

「√n 以下の素数で割る」版、「篩」版、そして「シンプルに √n 以下の整数で割る」版を実行してみた結果は以下のようになった。

[imac] mnbi% rm primes.txt
[imac] mnbi% time ./listprimes_binsearch.rb 100000 100
START (99991):
100003 (66)
100019 (66)
100043 (66)
100049 (66)
100057 (66)
100069 (66)
Elapsed: 0.000275
./listprimes_binsearch.rb 100000 100  17.60s user 0.02s system 100% cpu 17.601 total
[imac] mnbi% time ./listprimes_sieve.rb 100000 100
100003
100019
100043
100049
100057
100069
Elapsed: 0.019148
./listprimes_sieve.rb 100000 100  0.02s user 0.00s system 83% cpu 0.033 total
[imac] mnbi% time ./listprimes_simple.rb 100000 100
100003 (158)
100019 (158)
100043 (158)
100049 (158)
100057 (158)
100069 (158)
Elapsed: 0.00028
./listprimes_simple.rb 100000 100  0.01s user 0.01s system 89% cpu 0.020 total

「篩」版は確かに速いが、「シンプル」版はさらに速い。

もっとも、これは表示させる領域を大きな数を基点として「狭めて」いるから起きることだ。1 から 100000 までの範囲の素数を列挙するなら「シンプル版」の方が遅くなる。

一番、速いのは

範囲(それも比較的大きな数から始まるものを)を指定して列挙させる場合、速いのは「√n 以下の整数で割る」方法をシンプルに実装したものだ。2 から始まる素数表を生成する方式では、範囲の上限に至るまでのすべての素数を生成する分不利になる。

	#!/opt/local/bin/ruby1.9 -w
	# -*- coding: utf-8 -*-
	# listprime.rb: make a list of prime numbers.
	require 'prime'
	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
	def prime(n)
	return [false, 1] if n.even?
	c = 1
	d = 3
	limit = Math::sqrt(n)
	while d <= limit
	return [false, c] if (n % d == 0)
	c += 1
	d += 2
	end
	[true, c]
	end
	t0 = Time.now
	(start...(start + range)).each do |n|
	result = prime(n)
	print "#{n} (#{result[1]})\n" if result[0]
	end
	elapsed = Time.now - t0
	print "Elapsed: #{elapsed}\n"

view raw listprimes_simple.rb hosted with ❤ by GitHub

たとえば、画面に一定範囲にふくまれる素数を表示する(だけの)アプリを作るとしたら、素数表を作る方式は適さないことになる。画面に表示できる範囲は限られているのだから、素数表を(作って)保持しておくより、見えている分だけをシンプルな方法(√n 以下の整数で割る)で判定する方がずっと素早く表示できるはずだ。

関連リンク

• エラトステネスの篩 (Wikipedia:ja)
• 二分探索 (同上)

関連記事

• 素数を列挙する