0009: Prime Number

素数

問題ページ

解き方

エラトステネスの篩を使って素数のリストを用意し、そこから素数の値のみを取り出したリストを作る。

pytry3g.hatenablog.com

そして受け取った入力ｎに対して、そのｎ以下の素数の数を出力する。

いろいろやり方はあると思うが今回は二分探索法を提供しているライブラリのbisectを使う。bisectを使えばある数ｎをソート済みのリストのどこに挿入すべきかを探索してくれる。

コード(python)

import bisect

primes = [0, 0] + [1] * 999999
for i in range(2, 1000):
    if primes[i]:
        for j in range(i*i, 1000000, i):
            primes[j] = 0

primes = [i for i, v in enumerate(primes) if v]
while True:
    try:
        n = int(input())
    except:
        break
    print(bisect.bisect(primes, n))