N 以下の素数の個数

数と計算
問題 08
やさしい
目安 11 分

「n 以下の素数はいくつあるか」という質問が何度も与えられる。素数を 1 つずつ割って確かめず、先にまとめてふるい分けておく練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 3 秒までです。

問題

素数は、2 以上の整数のうち、1 とその数自身のほかに割り切れる正の整数を持たない数です。2、3、5、7、11 などが素数で、1 は素数ではありません。

Q 個の質問が与えられます。i 番目の質問は 1 つの整数 n_i で、「1 以上 n_i 以下の整数のうち、素数はいくつあるか」を表します。質問のそれぞれに、答えを 1 行ずつ出力してください。

入力の形式

Q
n_1
n_2
...
n_Q

1 行目に質問の数 Q、2 行目から Q 行に、1 行に 1 つずつ n_i が並びます。

出力の形式

Q 行を出力します。i 行目に、n_i 以下の素数の個数を書きます。

制約

Q は、1 以上 100000 以下の整数です
n_i は、1 以上 2000000 以下の整数です
同じ n_i が何度出てくることもあります

入力と出力の例

例 1

10 以下の素数は 2、3、5、7 の 4 個です。2 以下なら 2 だけで 1 個、20 以下なら 11、13、17、19 も加わって 8 個です。

入力

出力

4
1
8

例 2

1 は素数ではないので、1 以下の素数は 0 個です。

入力

2
1
100

出力

0
25

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

質問の中の最大の値を m として、m までの数をエラトステネスのふるいで素数かどうかに分けます。p が素数なら p × p から p ごとに消します (p × p より小さい p の倍数は、もっと小さい素数ですでに消えています)。そのあと、素数の個数を先頭から足した並び count を作ると、n_i 以下の素数の個数は count[n_i] です。

Python

import sys
from itertools import accumulate

data = sys.stdin.read().split()
q = int(data[0])
queries = list(map(int, data[1:1 + q]))
m = max(queries)

is_prime = bytearray([1]) * (m + 1)
is_prime[0] = 0
is_prime[1] = 0
p = 2
while p * p <= m:
    if is_prime[p]:
        is_prime[p * p::p] = bytes(len(range(p * p, m + 1, p)))
    p += 1

count = list(accumulate(is_prime))
print("\n".join(str(count[n]) for n in queries))

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const q = data[0];
const queries = data.slice(1, 1 + q);
let m = 0;
for (const n of queries) if (n > m) m = n;

const isPrime = new Uint8Array(m + 1).fill(1);
isPrime[0] = 0;
isPrime[1] = 0;
for (let p = 2; p * p <= m; p++) {
  if (!isPrime[p]) continue;
  for (let k = p * p; k <= m; k += p) isPrime[k] = 0;
}

const count = new Int32Array(m + 1);
for (let x = 1; x <= m; x++) count[x] = count[x - 1] + isPrime[x];

console.log(queries.map((n) => count[n]).join("\n"));

計算量

ふるいは O(M log log M) で、M は質問の中の最大の n です。個数の並びを作るのが O(M)、質問に答えるのは 1 つ O(1) なので、全部で O(M log log M + Q) です。

遅い解き方は、質問のたびに 2 から n_i までの数を 1 つずつ割って素数か確かめる書き方です。1 つの数に最大で √n 回の割り算がかかり、1 つの質問で O(n √n)、全部で O(Q × n √n) になります。n が 200 万の質問が 10 万個あるテストでは、どの言語でも時間切れになります。

よくある間違い

1 を素数として数えてしまう。表の 0 番と 1 番は、はじめに素数でないにしておきます
素数か確かめる割り算を x まで (あるいは x - 1 まで) 回してしまい、1 つの数に x 回かかる。割る数は 2 乗して x を越えないところまでで足ります
ふるいの表を、質問ごとに作り直してしまう。表は最大の n まで 1 回作れば、全部の質問に使えます
Python でふるいの表をふつうのリストで持ち、200 万回の代入を 1 つずつ書いて遅くなる。bytearray とスライスへの代入でまとめて消すと速く書けます

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
q = int(data[0])
queries = list(map(int, data[1:1 + q]))

# ここから書く

入力

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します