どん底から這い上がるまでの記録

どん底から這い上がりたいけど這い上がれない人がいろいろ書くブログ(主にプログラミング)

0009: Prime Number

 

素数

問題ページ

解き方

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

pytry3g.hatenablog.com

 

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

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

コード(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))