Sieve of Sundaram algorithm

prime_Sundaram.rb

##### Sieve of Sundaram algorithm
def prime_Sundaram(n)
  n = n/2
  a = []
  a[n] = nil

  t = (Math.sqrt(4+8*n)-2)/4
  u = 0
  r = []

  for i in 1..t do
    u = (n-i)/(1+2*i)
    for j in i..u do
      a[i + j + 2*i*j] = true
    end
  end

  for i in 0..n do
    r.push(i*2+1) if !a[i] 
  end
  
  puts r
end

# 測時間_2
require 'benchmark'
Benchmark.bm do |x|
  x.report do
    prime_Sundaram(1000000)
  end
end