소수 (Prime Number)

 

정의

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

“더 이상 쪼개지지 않는” 숫자로 볼 수 있고, 모든 자연수는 소수의 곱으로 표현됩니다. (소인수 분해)

그래서 소수는 수학뿐 아니라 컴퓨터 과학(특히 암호학)에서도 중요한 역할을 합니다.

핵심 메시지

“모든 자연수는 소수의 곱으로 표현된다.
소수는 숫자의 ‘기본 부품’이다.”

- 소인수분해의 출발점 -

성질

규칙이 단순하지만, 분포는 매우 복잡합니다.

• ✔️ 2는 유일한 짝수 소수이며, 그 외 모든 짝수는 합성수입니다.
• ✔️ 소인수분해: 모든 자연수는 소수의 곱으로 유일하게 표현됩니다(순서 제외).
• ✔️ 소수는 무한히 많습니다(유클리드의 증명 아이디어).

판별 방법

핵심은 √n까지만 나눠 보면 된다는 점입니다.

어떤 수 n이 합성수라면 n = a × b 형태로 표현됩니다. 이때 a와 b 중 최소 하나는 √n 이하이므로, 2부터 √n까지 나눠 떨어지는지 검사하면 충분합니다.

방법	복잡도	언제 쓰나
√n 검사	O(√n)	n 하나를 판별할 때(단일 입력)
에라토스테네스의 체	O(n log log n)	1~N까지 소수를 한 번에 구할 때(범위 입력)

생성 방법

범위의 소수를 구할 땐 에라토스테네스의 체가 표준입니다.

체(sieve)는 2부터 시작해 배수를 지우는 방식으로 소수를 찾습니다. “어떤 수의 배수는 소수가 아니다”라는 규칙을 이용해 한 번에 많은 수를 걸러낼 수 있습니다.

활용

암호학, 해시, 수론 기반 알고리즘에서 자주 등장합니다.

• ✔️ RSA 같은 공개키 암호: 큰 소수와 소인수분해의 어려움을 이용
• ✔️ 해시 테이블: 테이블 크기를 소수로 잡아 충돌 패턴을 줄이는 경우가 있음
• ✔️ 모듈러 연산: 소수 모듈러는 역원 계산 등에서 성질이 좋아 알고리즘에 자주 쓰임

주의점

소수 판별은 입력 크기에 따라 알고리즘 선택이 달라져야 합니다.

작은 범위에서는 √n 판별이나 체로 충분하지만, 암호학처럼 매우 큰 수에서는 확률적 판별(예: Miller–Rabin) 같은 방법을 사용합니다. 또한 1은 소수가 아니며, 2만 짝수 소수라는 기본 규칙을 코드에서 자주 놓칩니다.

코드

자바로 구현하였습니다.

class isPrime {
    static boolean isPrime(int N) {
        if (N <= 1) return false;       
        if (N == 2) return true;         
        if (N % 2 == 0) return false;

        for (int i = 3; i <= Math.sqrt(N); i += 2) {
            if (N % i == 0) {
                return false;
            }
        }
        return true;
    }
}

핵심 요약

한 번에 정리

✅ 핵심 요약

• ✔️ 소수는 1과 자기 자신만 약수를 가지는 2 이상의 자연수다.
• ✔️ 합성수 판별은 √n까지만 검사하면 충분하며, 범위는 에라토스테네스의 체가 효율적이다.
• ✔️ 소수는 소인수분해의 기반이며, 암호/해시/모듈러 연산 등 컴퓨터 과학에서 자주 활용된다.