n以下の素数の個数を高速に求めるには？

pi(n)をn以下の素数の個数と定義します。
pi(n)の正確な値を高速に求めるにはどのようなアルゴリズムを用いればよいでしょうか。

2×√n 程度のデータを用いて計算するコードを記しておきます。

(Ruby 2.2)

def pi(n)
  m = Math.sqrt(n).to_i
  keys = (1..m).map{|i| n / i}
  keys += (1..keys[-1] - 1).to_a.reverse
  h = {}
  # 1を除いた個数
  keys.each{|i| h[i] = i - 1}
  # 「素数」もしくは「i以下の素数では割り切れない合成数」の個数
  (2..m).each{|i|
    if h[i] > h[i - 1] # このときiは素数
      hp = h[i - 1]
      i2 = i * i
      keys.each{|j|
        break if j < i2
        h[j] -= h[j / i] - hp # iで初めて割り切れる合成数(ちなみにi2以上）を除く
      }
    end
  }
  h[n]
end

p pi(10 ** 8)

(Python 2.7)

import math

def pi(n):
    m = int(math.sqrt(n))
    keys = [n // i for i in range(1, m + 1)]
    keys += range(keys[-1] - 1, 0, -1)
    h = {i : i - 1 for i in keys}
    for i in range(2, m + 1):
        if h[i] > h[i - 1]:
            hp = h[i - 1]
            i2 = i * i
            for j in keys:
                if j < i2: break
                h[j] -= h[j // i] - hp

    return h[n]

print pi(10 ** 8)

（参考）
(Ruby 2.2)
上記コードと、Rosetta Code で紹介されている Wheel factorization を用いた方法
（http://rosettacode.org/wiki/Sieve_of_Eratosthenes#With_a_wheel）とで比較してみた。

require 'benchmark'
puts Benchmark::CAPTION
puts Benchmark.measure{
  p pi(10 ** 8)
}
puts Benchmark.measure{
  p eratosthenes2(10 ** 8).size
}

おおよそ以下のような結果になります。

      user     system      total        real
5761455
  0.218000   0.000000   0.218000 (  0.210384)
5761455
  8.362000   0.312000   8.674000 (  8.699177)

速さで比較すると、
上記コード＞ Wheel factorization を用いた方法（＞エラトステネスの篩）
となっている。