Day 002-Q2 | 素数判定

問題

整数 N が与えられる。N が素数かどうかを判定せよ。T 個のテストケースが与えられるので、それぞれについて答えよ。

入力形式

T
N_1
N_2
...
N_T

制約

$1 \le T \le 100$

$2 \le N_i \le 10^9$

入出力例

入力例 1

出力例 1

Yes
Yes
No
Yes
No

ヒント (段階的開示)

ヒント1: 方向性

2〜N-1 全て試すと N=10^9 では遅すぎる。

ヒント2: アプローチ

N が合成数なら √N 以下の素因数を必ず持つ → 2 から √N まで試せば十分（O(√N) ≈ 31623回）。

ヒント3: 誘導

import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

模範解答 (Python)

import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

T = int(input())
for _ in range(T):
    N = int(input())
    print("Yes" if is_prime(N) else "No")

Step-by-Step 解説

1なぜ √N まで調べれば十分か
N が合成数なら N = a × b（a ≤ b）と書ける。このとき a ≤ √N が成り立つ。よって √N 以下の約数だけ確認すれば十分。

2関数の実装
n < 2 は素数でない。range(2, int(sqrt(n)) + 1) で +1 を忘れない（N=9 の3を含めるため）。

3T個のテストケースを処理
三項演算子 "Yes" if is_prime(N) else "No" でシンプルに記述。

計算量

1クエリ: $O(\sqrt{N})$ — N=10^9 で約 31623 回
合計: $O(T \cdot \sqrt{N})$ — T=100 なら約 316万回

よくあるミス

ミス	原因	正しい書き方
`range(2, n)`	N=10^9 でTLE	`range(2, int(sqrt(n)) + 1)`
`+1` 忘れ	N=9 の3を確認しない	`int(math.sqrt(n)) + 1`
n=1 の扱い	1は素数でない	`if n < 2: return False`

Day 002-Q2 — 素数判定

問題