上のソースでは探索範囲1つにつき true/false を作るので、1億まで探索しようと思うとかなりのメモリが必要となる。どうせ真偽値なのだから、BitArray を用いれば候補一つにつき 1bit で済む。また、偶数はどうせ素数ではないので、奇数のみを探索対象にする…

なんか、エラトステネスの篩を用いていると言いつつ試行割算法を混同していたり、エラトステネスの篩を用いつつもハッシュを使ったりして速度を落としている例が多いような。エラトステネスの篩では加算しか使わない。だから速い、圧倒的に。 追記: もっとも…

def _sieve(primes, min=3, size=1_0000_0000) table = "\xFF" * (size / 8 + 1) max = min + size * 2 - 1 tmax = size mid = Math.sqrt(max).floor primes.each do |i| next if i > mid ti = (i - min) / 2 ti += i while ti < 0 ti.step(tmax, i) do |tj|…