소수 판정 · 알고리즘 노트

개념

소수는 $1$ 과 자기 자신만을 약수로 가지는 $2$ 이상의 자연수입니다. $1$ 은 소수가 아닙니다.

약수로 소수 판별하기

$2$ 이상의 자연수 중 소수가 아닌 수를 합성수라고 합니다. 합성수 $N$ 은 $N=ab$ 인 두 자연수 $a,b>1$ 로 나눌 수 있습니다. 두 인수가 모두 $\sqrt N$ 보다 크면 $ab>N$ 이 되므로, 적어도 한 인수는 $\sqrt N$ 이하여야 합니다.

따라서 $2$ 부터 제곱근까지 나누어떨어지는 수가 하나라도 있으면 합성수이고, 하나도 없으면 소수입니다. $2$ 와 $3$ 은 이 범위에 검사할 수가 없으며 둘 다 소수입니다. $1$ 은 소수의 정의에서 제외합니다.

$29$ 는 $2,3,4,5$ 중 어느 수로도 나누어떨어지지 않으므로 소수입니다. $35$ 는 $5$ 로 나누어떨어지므로 합성수입니다.

한 수 또는 몇 개의 수만 판정할 때는 이 방법을 사용할 수 있습니다. 예를 들어 $10000$ 미만의 한 수라면 $100$ 미만의 후보만 확인합니다. 일정 범위의 모든 수를 판정하거나 같은 범위의 수가 소수인지 여러 번 확인할 때는 에라토스테네스의 체로 각 수의 소수 여부를 미리 저장해 둘 수 있습니다.

복잡도

판별할 자연수를 $N$ 이라고 합니다.

연산	시간복잡도	공간복잡도
소수 판별	$O(\sqrt N)$	추가 $O(1)$

예제

문제

주어진 양의 정수가 소수인지 판별하여라.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다. $1\le N\le9\,999$ 이다.

출력

소수이면 YES, 아니면 NO를 출력한다.

예제 코드

C++20

#include <iostream>

using namespace std;

int main() {
    int n, i;
    bool ok;

    cin >> n;
    ok = n >= 2;
    for (i = 2; i <= n / i; ++i) {
        if (n % i == 0) ok = false;
    }

    cout << (ok ? "YES" : "NO") << '\n';
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int n, i;
        boolean ok;

        in = new Scanner(System.in);
        n = in.nextInt();
        ok = n >= 2;
        for (i = 2; i <= n / i; ++i) {
            if (n % i == 0) ok = false;
        }

        System.out.println(ok ? "YES" : "NO");
    }
}

Python 3

n = int(input())
ok = n >= 2
i = 2

while i * i <= n:
    if n % i == 0:
        ok = False
    i += 1

print("YES" if ok else "NO")

2.2.2 Primality Test

개념

약수로 소수 판별하기

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드