読者です 読者をやめる 読者になる 読者になる

エラトステネスの篩

なんか、エラトステネスの篩を用いていると言いつつ試行割算法を混同していたり、エラトステネスの篩を用いつつもハッシュを使ったりして速度を落としている例が多いような。エラトステネスの篩では加算しか使わない。だから速い、圧倒的に。
追記: もっとも、肝は真偽値テーブルを使うことで、一つ一つ候補を見なくて済む、篩の手法だから。割り算を排除すれば速くなるかというと、そうでもない。 (割り算がある所は高速化の余地があるというのは確かだけど)

def sieve_simple(max)
  primes = []
  table = Array.new(max+1).fill(true, 2);
  mid = Math.sqrt(max).floor
  (2..mid).each do |i|
    if table[i]
      primes << i
      (i+i).step(max, i) do |j|
	table[j] = false if table[j]
      end
    end
  end
  ((mid+1)..max).each{|i|primes << i if table[i]}
  primes
end

多くの人のコードに存在する、n % prime == 0 が存在しないのがポイント。メモリ消費量は max+1bit なので、100万までとしても最少 数百KB となる。 (Ruby の Array だと意味ないけど、BitArray のある言語だと大きな違いになるでしょう)
ちなみに、Pentium M 1.60GHz 1GB RAM Windows XP ruby 1.9 (mingw32) で 2.298 秒でした。
参考: エラトステネスの篩 - Wikipedia