エラトステネスのふるい

x = 10001000
 
sample_numbers = (2 .. x).to_a
prime_numbers = [2]
 
while not sample_numbers.empty? do
 
    max_prime_number = prime_numbers.last
 
    # 素数で割れるものを除外
    sample_numbers = sample_numbers.reject { |i|
        i % max_prime_number == 0
    }
 
    # 残ったものの最初の数が素数
    prime_numbers << sample_numbers.shift
 
    # 検査する数の最後が、最大の素数の平方より小さければ、残りは全部素数
    if sample_numbers.last < prime_numbers.last ** 2
        prime_numbers << sample_numbers
        prime_numbers.flatten!
        break
    end
end
 
prime_numbers.each do |p|
 puts p
end