160302

Ruby

素数の個数(7)

オンライン整数列大辞典の
A000720（http://oeis.org/A000720/list）
と比較し、答え合わせしてみる。

def pi(n)
  return [0] if n == 0
  a = Array.new(n + 1, 1)
  l = 0
  a[0] = l
  a[1] = l
  i = 2

  while i * i <= n
    # 素数のとき
    if a[i] == 1
      l += 1
      j = i + i
      while j <= n
        a[j] = 0
        j += i
      end
    end
    a[i] = l
    i += 1
  end

  while i <= n
    # 素数のとき
    if a[i] == 1
      l += 1
    end
    a[i] = l
    i += 1
  end
  a
end

def A000720(n)
  pi(n)[1..-1]
end
ary = A000720(78)

# OEIS A000720のデータ
ary0 =
[0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8,8,8,9,9,
 9,9,9,9,10,10,11,11,11,11,11,11,12,12,12,12,13,13,
 14,14,14,14,15,15,15,15,15,15,16,16,16,16,16,16,
 17,17,18,18,18,18,18,18,19,19,19,19,20,20,21,21,
 21,21,21,21]
# 一致の確認
p ary == ary0