합성수(Composite Number)

정의

1과 자기 자신 이외의 약수를 가지는 자연수(2 이상)입니다.

 어떤 자연수 n이 1과 n 말고도 나누어떨어지는 수가 있으면 합성수입니다.

합성수 ⇔ ∃ a(2 ≤ a ≤ n-1), n % a == 0

예) 4( = 2×2), 6( = 2×3), 9( = 3×3), 12( = 3×4) …

핵심 메시지

합성수 판별은 “약수가 하나라도 더 있는지”를 찾는 문제입니다.
이때 √n까지만 확인해도 충분하다는 성질이 알고리즘 최적화의 핵심입니다.

수학 개념

합성수,  소수,  1의 관계

1은 소수도 합성수도 아니다

소수는 “약수가 정확히 2개(1과 자기 자신)”인 수, 합성수는 “약수가 3개 이상”인 수입니다.

1은 약수가 1개(자기 자신만)이므로 소수/합성수 어느 쪽에도 속하지 않습니다.

합성수는 소인수 분해가 가능하다

모든 합성수는 두 개 이상의 소수의 곱으로 표현됩니다(소인수분해). 예) 12 = 2²×3, 18 = 2×3², 45 = 3²×5

√n까지만 검사해도 되는 이유

n이 합성수라면 n = a×b 형태로 쓸 수 있고, 이때 a와 b 중 하나는 반드시 √n 이하입니다.

그래서 약수를 찾을 때는 2부터 √n까지만 확인하면 됩니다.

n이 합성수 ⇒ ∃ a (2 ≤ a ≤ √n), n % a == 0

구분	약수 개수	예시
소수	정확히 2개	2, 3, 5, 7, 11…
합성수	3개 이상	4, 6, 8, 9, 10, 12…
1	1개	1

알고리즘 개념

합성수 판별 2가지: √n 검사 vs 에라토스테네스의 체

1) 단일 수 판별 : 2부터 √n까지 나눠보기

한 개의 숫자가 합성수인지 확인할 때는 2..√n만 검사해도 됩니다.

이 방식은 구현이 간단하고, 입력이 한 번만 들어오는 문제에서 자주 쓰입니다.

시간복잡도: O(√n)

2) 구간 판별: 에라토스테네스의 체(Prime Sieve)

1부터 N까지 “합성수/소수”를 한꺼번에 구해야 한다면 체(sieve)가 표준입니다.

소수의 배수들을 지워가며 합성수를 표시합니다.

시간복잡도(대표): O(N log log N)

구현

Java로 합성수 판별하기

TIP

반복 조건을 i * i <= n 형태로 쓰면, sqrt 호출 없이도 √n까지만 탐색할 수 있습니다. (단, n이 큰 long 범위면 overflow에 주의)

1) 단일 수가 합성수인지 확인 (O(√n))

public class CompositeCheck {

    static boolean isComposite(int n) {
        if (n <= 1) return false; // 1은 합성수가 아님(정의상)
        if (n == 2) return false; // 2는 소수
        if (n % 2 == 0) return true; // 2보다 큰 짝수는 합성수

        for (int i = 3; i * i <= n; i += 2) { // 홀수만 검사
            if (n % i == 0) return true;
        }
        return false; // 약수가 없으면 소수
    }

    public static void main(String[] args) {
        System.out.println(isComposite(1));  // false
        System.out.println(isComposite(2));  // false
        System.out.println(isComposite(9));  // true
        System.out.println(isComposite(17)); // false
    }
}

2) 1..N 구간에서 합성수 표시 (에라토스테네스의 체)

import java.util.*;

public class CompositeSieve {

    // isComposite[i] == true  -> i는 합성수
    static boolean[] sieveComposite(int n) {
        boolean[] isComposite = new boolean[n + 1];
        if (n >= 0) isComposite[0] = true;
        if (n >= 1) isComposite[1] = true;

        for (int i = 2; i * i <= n; i++) {
            if (!isComposite[i]) { // i가 소수라면
                for (int j = i * i; j <= n; j += i) {
                    isComposite[j] = true; // i의 배수는 합성수
                }
            }
        }
        return isComposite;
    }

    public static void main(String[] args) {
        int N = 30;
        boolean[] comp = sieveComposite(N);

        List<Integer> composites = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (comp[i]) composites.add(i);
        }
        System.out.println(composites); // [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30]
    }
}

요약

체크리스트로 마무리

CHECK

✅ 합성수: 1과 자기 자신 외의 약수를 가지는 자연수(2 이상)

✅ 1은 소수도 합성수도 아님

✅ 단일 판별은 2..√n만 검사하면 충분 (O(√n))

✅ 구간 판별은 에라토스테네스의 체 (대략 O(N log log N))