Rubyの組み込みPrimeで実装されているエラトステネスのふるいの解説　https://github.com/ruby/ruby/blob/3e92b635fb5422207b7bbdc924e292e51e21f040/lib/prime.rb#L422

eratosthenes_sieve.rb

=begin

## エラトステネスのふるい とは

エラトステネスのふるいは、x^(1/2) 以下の素数が既知のとき、
x^(1/2) 以上 x 以下の素数を決定するには、x 以下の整数で
x^(1/2) 以下の素数の倍数を全て取り除けばよいというものです


## なぜ組み込みのエラトステネスのふるい は早いのか

[Segmented Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve)
を実装している点と、indexを使って1/2個の配列にアクセスして更新しており、
配列の再生成をできるだけ少なくしているからだと思われます。



## 概要

EratosthenesSieveの@primesから素数を取り出すというのが基本的な動き。
@primesは配列なのでindexでアクセスして取り出している。

PseudoPrimeGeneratorで実装されたブロックを継承していて、
succでindexを更新しながら素数を取り出している。

=end


class EratosthenesSieve
  include Singleton

  def initialize
    @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
    # @max_checked must be an even number
    @max_checked = @primes.last + 1
  end

  def get_nth_prime(n)
    compute_primes while @primes.size <= n
    @primes[n]
  end

  private
  def compute_primes
    # max_segment_size must be an even number
    max_segment_size = 1e6.to_i
    max_cached_prime = @primes.last

    puts "max_segment_size: #{max_segment_size}"
    puts "max_cached_prime: #{max_cached_prime}"

    # 素数は、+1すると偶数で、必ず2で割れるため、チェック済みとしている
    @max_checked = max_cached_prime + 1 if max_cached_prime > @max_checked
    puts "@max_checked: #{@max_checked}"

    segment_min = @max_checked
    # 基本的にはキャッシュされた素数の2倍ずつ配列を増やす
    # 100万を超えたら、配列のサイズが大きくなりすぎるので100万ずつ増やしていく
    segment_max = [segment_min + max_segment_size, max_cached_prime * 2].min
    root = Integer(Math.sqrt(segment_max).floor)
    puts "segment_min: #{segment_min}"
    puts "segment_max: #{segment_max}"
    puts "root: #{root}"

    # segment_min(= @max_checked = 偶数)のため、奇数から始める
    # 偶数を飛ばすためstep(2)している
    segment = ((segment_min + 1) .. segment_max).step(2).to_a
    puts "segment: #{segment}"

    # prime = 3のとき
    # indexを3ずつ飛ばして行くとちょうど3の倍数になる
    # 3の倍数は3 * n (n = 1, 2, 3, ..., x)で表現できる
    # 今回はstep(2)で偶数をすべて飛ばしているので
    # 3 * n (n = 1, 3, 5, ..., x) の奇数列の倍数のみを考えれば良い
    (1..Float::INFINITY).each do |sieving|
      prime = @primes[sieving]
      break if prime > root
      composite_index = (-(segment_min + 1 + prime) / 2) % prime
      while composite_index < segment.size do
        puts "  composite_index: #{composite_index}"
        puts "  prime: #{prime}"
        puts "  nil segment: #{segment[composite_index]}\n ===="
        segment[composite_index] = nil
        composite_index += prime
      end
    end


    p segment.compact
    @primes.concat(segment.compact!)

    @max_checked = segment_max
  end
end



# max_num = 202
max_num = 101

def each_count(max_num)
  primes = []
  last_value = nil
  # EratosthenesSieveの@primesにindexアクセスする
  # @primesにloopで0番目から、+1しながらアクセスするために-1でセットしている
  n = -1
  loop do
    n += 1
    prime = EratosthenesSieve.instance.get_nth_prime(n)
    # when max_num < 101;  get_nth_primeでwhileをすぐ抜けてn番目にアクセスする
    # when max_num >= 101; get_nth_primeのwhileでnになるまでcompute_primes
    if prime > max_num
      break primes.size
    end
    primes << prime
    last_value = prime
  end
end


p '# current prime: ' + each_count(max_num).to_s