약수 (Divisor)

정의

어떤 정수 n을 나누었을 때 나머지가 0이 되는 정수입니다.

 약수는 단순한 개념이지만, 소인수분해/최대공약수/최소공배수/배수 판정 같은 주제의 기본 재료가 됩니다.

예를 들어 12의 약수는 1, 2, 3, 4, 6, 12 입니다.

핵심 메시지

“약수는 ‘나눗셈 결과’가 아니라,
곱셈 구조(n = a × b)를 읽는 도구다.”

- 약수는 곱의 짝(pair)로 나타난다 -

핵심 성질

항상 짝(pair)으로 나타나며, 경계는 √n입니다.

n = a × b라면 a가 약수일 때 b도 약수입니다. 즉 약수는 (a, b)처럼 짝으로 묶입니다. 그리고 a ≤ b라고 하면 a는 반드시 √n 이하입니다. 그래서 약수를 찾을 때는 1부터 √n까지만 검사해도 전체 약수를 얻을 수 있습니다.

구하는 방법

약수 열거는 보통 √n 순회로 해결합니다.

i를 1부터 √n까지 증가시키며 n % i == 0이면 i는 약수입니다. 이때 함께 나오는 짝 약수는 n / i 입니다. 만약 i == n / i(즉 i² == n)라면 제곱수이므로 중복을 피해야 합니다.

방법	복잡도	특징
1~n 전수	O(n)	n이 작을 때만 가능
√n 순회	O(√n)	실무/코테에서 표준, 짝 약수까지 함께 얻음

💡 TIP / 정렬

√n 순회로 얻는 약수는 “작은 약수(i)”와 “큰 약수(n/i)”가 섞여 나옵니다. 오름차순이 필요하면 작은 약수는 리스트에, 큰 약수는 스택(또는 별도 리스트)에 담아 뒤집어서 합치면 정렬을 쉽게 맞출 수 있습니다.

약수의 개수

소인수분해가 되면 약수 개수는 (지수+1)의 곱으로 계산됩니다.

n = p₁^a × p₂^b × ... 라고 소인수분해할 수 있다면, 약수의 개수는 (a+1)(b+1)... 입니다. 이유는 각 소수 pᵢ에 대해 지수를 0~a 범위로 선택할 수 있기 때문입니다.

예시
360 = 2³ × 3² × 5¹
약수 개수 = (3+1)(2+1)(1+1) = 4×3×2 = 24개

활용

약수는 GCD/LCM, 배수 판정, 약수 합 같은 문제의 핵심입니다.

• ✔️ 최대공약수(GCD): 공통 약수 중 가장 큰 값
• ✔️ 최소공배수(LCM): 공통 배수 중 가장 작은 값(보통 lcm = a×b/gcd)
• ✔️ 약수의 합: 소인수분해/등비수열을 이용해 빠르게 계산 가능

코드

자바로 구현하였습니다.

import java.util.*;

public class DivisorsSqrt {
    public static List<Integer> divisors(int n) {
        List<Integer> small = new ArrayList<>();
        List<Integer> large = new ArrayList<>();

        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                small.add(i);
                int pair = n / i;
                if (pair != i) large.add(pair); // 제곱수면 중복 방지
            }
        }

        // 오름차순으로 만들려면 large는 역순으로 붙이면 됨
        Collections.reverse(large);
        small.addAll(large);
        return small;
    }

    public static void main(String[] args) {
        int n = 36;
        System.out.println(divisors(n)); // [1, 2, 3, 4, 6, 9, 12, 18, 36]
    }
}

주의점

제곱수는 중복, 큰 수는 시간/오버플로우를 조심해야 합니다.

√n 순회에서 i² = n인 경우(i == n/i)는 약수가 하나만 추가되어야 합니다(중복 방지). 또 약수/배수 계산에서 a×b가 int 범위를 넘을 수 있으니 long 사용을 고려해야 합니다.

핵심 요약

한 번에 정리

✅ 핵심 요약

• ✔️ 약수는 n을 나눴을 때 나머지가 0인 정수이며, 약수는 항상 짝(pair)으로 나온다.
• ✔️ 약수 열거는 √n까지만 검사하면 충분하고, 제곱수는 중복을 주의한다.
• ✔️ 소인수분해가 있으면 약수 개수는 (지수+1)의 곱으로 계산되며, GCD/LCM 등 핵심 문제로 연결된다.