素数を求める

## エラトステネスのふるいを用いて素数を求める
def getPrime(num)
  return [2] if num == 2
  return [2, 3] if num == 3

  rootPrime = getPrime(Math.sqrt(num).floor)
  eratosu(rootPrime, num)
end

## エラトステネスのふるい
## rootPrime:numの平方根より小さい素数
## num:求めたい素数の最大
def eratosu(rootPrime, num)
  # idxがふるいにかける数、val=1が素数、val=0が素数じゃない
  # 0と1は素数じゃない
  primeCand = Array.new(num, 1)
  primeCand[0] = 0 
  primeCand[1] = 0

  # 素数の定数倍を削除
  rootPrime.each do |el|
    i = el
    while el * i < num
      primeCand[el * i] = 0
      i += 1
    end
  end

  primeCand.each_index.select { |i| primeCand[i] == 1 }
end