Volume0: 0009

素数 | Aizu Online Judge

以下の素数の個数を求める問題です。

予めエラトステネスの篩を使用して素数のリストを作成しておき、各データセットに対して素数の個数を求めます。

Python

# coding: utf-8

LIMIT = 999999

# 1 から LIMIT までのリスト
# 素数（の候補）を 1 、素数でないもを 0 とする  
# 2 以外の偶数は素数ではない
prime = [0, 1] + [0 if i % 2 == 0 else 1 for i in range(3, LIMIT + 1)]

# 3 から LIMIT の平方根までを走査
for i in range(3, int(LIMIT ** 0.5) + 1):
    # 対象が素数である場合
    if prime[i - 1] == 1:
        # 自身の倍数は素数ではない
        for j in range(i ** 2, LIMIT + 1, i):
            # 素数ではないので 0
            prime[j - 1] = 0

while True:
    try:
        n = int(input())
    except EOFError:
        break
    
    # 1 から n までの素数の個数を合計して出力
    print(sum(prime[:n]))

Ruby

Primeクラスで素数についてあれこれできます。

# coding: utf-8

require 'prime'

while line = gets do
    n = line.to_i
    puts Prime.each(n).count
end