クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-6 素数の個数」(p.111)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 素数の個数」(p.111)
のコードをPythonで書き直したものとなっています。

入力


n

入力例1



11

入力例2



1000000


解答

MAX_N = 10 ** 6

prime = [None] * MAX_N    # i番目の素数
is_prime = [True] * (MAX_N + 1)    # is_prime[i]がTrueならiは素数

# n以下の素数の数を返す
def sieve(n):
    p = 0
    for i in range(n + 1):
        is_prime[i] = True
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime[p] = i
            p += 1
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return p

n = int(input())
ans = sieve(n)
print(ans)