← 브론즈 I

소수 판정

√N까지 나눠 보며 소수를 가려낸다.

수학

브론즈 I

선수 지식: 반복문 나머지 연산

1강 소수 판정의 개념과 √N 원리 공식

소수란?

소수(prime) 는 1과 자기 자신으로만 나누어지는, 1보다 큰 정수입니다(2, 3, 5,
7, 11, ...). "이 수가 소수인가?"를 빠르게 판단하는 법을 배웁니다.

1. 가장 단순한 방법

$$N$$ 이 2부터 $$N-1$$ 까지의 어떤 수로도 나누어지지 않으면 소수입니다.

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i++)
        if (n % i == 0) return false;   // 약수 발견 -> 소수 아님
    return true;
}

맞지만 $$O(N)$$ 이라 큰 수에선 느립니다.

2. 핵심 통찰: √N까지만 보면 된다

$$N$$ 이 $a \times b$ 로 쪼개진다면, $$a$$ 와 $$b$$ 중 하나는 반드시 $\sqrt{N}$ 이하입니다.
(둘 다 $\sqrt N$ 보다 크면 곱이 $$N$$ 을 넘으니까요.) 따라서 $\sqrt N$ 까지만 나눠
봐서 약수가 없으면 소수입니다.

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long long)i * i <= n; i++)   // i*i <= n  <=>  i <= √n
        if (n % i == 0) return false;
    return true;
}

i <= sqrt(n) 대신 i * i <= n 으로 쓰는 게 정확하고 안전합니다(실수 오차 회피).
이로써 $$O(N)$$ 이 $O(\sqrt N)$ 으로 확 줄어듭니다.

3. 복잡도 비교

방법	복잡도	$$N = 10^9$$ 일 때
2 ~ N-1	$$O(N)$$	약 10억 번 (느림)
2 ~ √N	$O(\sqrt N)$	약 3만 번 (빠름)

수 하나의 소수 판정이라면 $\sqrt N$ 방법으로 충분합니다.

4. 여러 수를 판정해야 한다면?

"1부터 N까지 각 수가 소수인지"처럼 범위 전체를 묻는다면, 하나씩 $\sqrt N$ 로
하는 것보다 에라토스테네스의 체가 훨씬 빠릅니다(다음 단계에서 별도 단원).
지금은 "수 하나 판정 = √N 방법"을 확실히 익히세요.

정리

소수 = 1과 자기 자신만 약수인 1 초과 정수.
1 이하는 소수 아님, 2는 가장 작은 소수.
$\sqrt N$ 까지만 나눠 보면 충분 — i * i <= n.
범위 전체를 묻는다면 체가 더 빠르다.

2강 소수 판정 구현과 연습 공식

소수 판정 구현 레퍼런스

올바른 √N 판정 함수와 자주 나오는 응용을 코드로 정리하고, 흔한 실수를 짚습니다.

1. 완성형 판정 함수

#include <bits/stdc++.h>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n; cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (isPrime(x)) cnt++;     // 소수 개수 세기
    }
    cout << cnt << '\n';
}

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

n = int(input())
cnt = sum(1 for x in map(int, input().split()) if is_prime(x))
print(cnt)

i * i <= n이 핵심입니다. i <= n ** 0.5(실수)는 오차로 경계에서 틀릴 수 있으니
정수 비교가 안전합니다.

2. 살짝 더 빠르게 (선택)

2만 따로 처리하고 이후 홀수만 검사하면 절반으로 줄어듭니다.

bool isPrime(long long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (long long i = 3; i * i <= n; i += 2)   // 홀수만
        if (n % i == 0) return false;
    return true;
}

3. 소인수분해에 응용

int n; cin >> n;
for (int i = 2; (long long)i * i <= n; i++)
    while (n % i == 0) {      // i로 더 안 나눠질 때까지
        cout << i << ' ';
        n /= i;
    }
if (n > 1) cout << n;         // 남은 큰 소인수

소수 판정과 같은 $\sqrt N$ 원리를 쓰는 단골 응용입니다.

4. 함정과 패턴 인식

1과 0, 음수 — 1 이하는 소수가 아님. n < 2 처리 필수.
i*i 오버플로 — n이 클 때 i*i가 int를 넘을 수 있음. long long 또는 i <= n/i.
실수 sqrt 오차 — i <= sqrt(n) 대신 i * i <= n.
범위 문제에 단건 판정 — 1~N 전부면 체를 쓰는 게 빠름.

문제에 "소수인지 판별", "소수의 개수", "소인수분해", "다음 소수" 같은 말이
보이면 이 단원입니다.

정리

소수 판정의 정석은 n < 2 거르고 i * i <= n까지 나눠 보는 것입니다. 큰 수엔
long long과 오버플로 주의, 범위 전체엔 에라토스테네스의 체 — 이것만 기억하면
Bronze~Silver의 소수 문제는 막힘이 없습니다.

방법	복잡도	$\(N = 10^9\)$ 일 때
2 ~ N-1	$\(O(N)\)$	약 10억 번 (느림)
2 ~ √N	$O(\sqrt N)$	약 3만 번 (빠름)