求某个范围内素数的个数

prime.rb

# 求某个范围内素数的个数
# 最大值不要超过1亿
def prime max_number
	nums = Array.new(max_number + 1, 1)
	sqrt_num = Math.sqrt(max_number).to_i
	(4...max_number).step(2) { |n| nums[n] = 0 }
	(3...sqrt_num).step(2) { |n| (n * 2...(max_number + 1)).step(n) { |m| nums[m] = 0 } if (nums[n] == 1) }
	return nums.count(1) - 2 # 去掉nums[0]和nums[1]
end

#===========================================================
# 以下是性能测试代码
#===========================================================

# 预热
prime(10000)

# 评测
require 'benchmark'

Benchmark.bm do |x|
   (4..8).each do |i|
      x.report(10**i){ prime(10**i) }
   end
end