코딩테스트 필수 도구: 소수찾기, 소인수분해, 최대공약수, 최소공배수

목차

• 1. 코딩 테스트 수학이 ‘공식 암기’가 아니라 ‘도구화’인 이유
• 2. 사전 준비: Map 기반 MathUtils 설계 포인트
• 3. 소수 판별 isPrime: √n 경계, 최적화, i*i 오버플로우 방어
• 4. 소인수 분해 getPrimeFactors(Map): 지수 맵으로 파생 수식 즉시 전개
• 5. 최대공약수 GCD: 유클리드 호제법, 배열 GCD, 약분/정규화
• 6. 최소공배수 LCM: 구현 순서, 오버플로우 감각, 배열 LCM
• 7. 실전 응용 패턴 6선: 문제 문장을 수식으로 번역하는 법
• 8. 요약: 언제 무엇을 꺼내 써야 할까?

코딩 테스트를 시작하면 수학 문제가 “공식 암기”처럼 보이는 순간이 옵니다. 하지만 실전에서 점수를 만드는 건 공식 그 자체가 아니라, 공식을 코드로 즉시 꺼내 쓰는 능력입니다. 특히 소수/소인수 분해/GCD/LCM은 독립된 주제가 아니라 서로 연결된 “핵심 수학 루틴”이며, 문제 문장을 읽는 즉시 올바른 루틴을 선택하는 것이 관건입니다.

이번 글은 여러분이 수정한 MathUtils(소인수 분해를 Map<소수, 지수>로 반환하는 버전)를 기준으로, 코딩 테스트에서 많이 쓰이는 수식을 구현 관점에서 해부하고, 파생 공식과 자주 쓰는 패턴을 예제 코드와 함께 정리합니다.

1. 코딩 테스트 수학이 ‘공식 암기’가 아니라 ‘도구화’인 이유

코딩 테스트 수학 문제는 크게 두 가지 형태로 출제됩니다.

• 직접형: “최대공약수/최소공배수/소수 여부/소인수”를 그대로 묻는다.
• 번역형: 문장 속 조건을 수식으로 바꿔야 한다. 예) “동시에 반복”, “나누어 떨어짐”, “최대로 단순화”, “서로소”, “약수의 개수”, “공통 주기”.

입문자들이 막히는 지점은 보통 수학 지식의 부족이 아니라, 문장 → 수식(루틴)으로의 변환 경험 부족입니다. 아래 키워드가 보이면, 거의 자동으로 연결되어야 합니다.

• “공약수”, “서로소”, “약분”, “비율 단순화” → GCD
• “주기”, “동시에”, “최초 공통 시점”, “공통 분모” → LCM
• “약수 개수/합”, “제곱수”, “서로 다른 소수 곱” → 소인수 분해(지수 맵)
• “소수인지” 또는 “소수만 추리기” → isPrime 또는 체

이제부터는 MathUtils를 “수학 엔진”으로 보고, 각 메서드가 어떤 수식을 담당하는지, 그리고 왜 그 구현이 실전에서 안전한지까지 같이 보겠습니다.

2. 사전 준비: Map 기반 MathUtils 설계 포인트

아래는 이번 글의 기준이 되는 MathUtils입니다. 코딩 테스트 관점에서 중요한 설계 포인트는 다음과 같습니다.

• 소인수 분해 결과를 Map<소수, 지수>로 반환: 파생 공식(약수 개수/합/φ/제곱수 판정)을 즉시 계산 가능
• (long)i*i 형태로 루프 조건 오버플로우 방어: 입력이 int 상한에 가까울 때도 안전
• GCD 결과 양수 정규화: 음수 입력이 섞여도 일관된 의미(공약수는 양수)를 유지
• LCM은 (a/gcd)*b 순서: 중간 곱 오버플로우 가능성을 줄이는 실전형 구현

MathUtils.java

import java.util.*;

class MathUtils {

  // 1) 소인수 분해: Map<prime, exponent>
  // - 코테에서 가장 실전적인 형태(약수개수/φ/약수합 등 바로 계산 가능)
  // - i*i 오버플로우 방지: (long)i*i 사용
  public static Map<Integer, Integer> getPrimeFactors(int n) {
    Map<Integer, Integer> exp = new LinkedHashMap<>();
    if (n < 2) return exp;

    for (int i = 2; (long) i * i <= n; i++) {
      while (n % i == 0) {
        exp.put(i, exp.getOrDefault(i, 0) + 1);
        n /= i;
      }
    }

    if (n > 1) exp.put(n, exp.getOrDefault(n, 0) + 1);
    return exp;
  }

  // 2) 소수 판별
  // - i*i 오버플로우 방지: (long)i*i 사용
  public static boolean isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

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

  // 3) GCD (int) - 결과 양수 정규화
  public static int getGCD(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);

    while (b != 0) {
      int r = a % b;
      a = b;
      b = r;
    }
    return a;
  }

  // 4) GCD (long) - 결과 양수 정규화
  public static long getGCD(long a, long b) {
    a = Math.abs(a);
    b = Math.abs(b);

    while (b != 0) {
      long r = a % b;
      a = b;
      b = r;
    }
    return a;
  }

  // 5) 배열 GCD
  public static int getGCD(int[] arr) {
    if (arr == null || arr.length == 0) return 0;

    int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
      result = getGCD(result, arr[i]);
      if (result == 1) return 1;
    }
    return Math.abs(result);
  }

  // 6) LCM (두 수)
  // - LCM은 보통 양수로 취급
  // - 중간 곱 오버플로우 완화: (x/g)*y 순서
  public static long getLCM(int a, int b) {
    if (a == 0 || b == 0) return 0;

    long x = Math.abs((long) a);
    long y = Math.abs((long) b);
    long g = getGCD(x, y);

    return (x / g) * y;
  }

  // 7) 배열 LCM
  // - 0이 하나라도 있으면 0
  // - 중간 곱 오버플로우 완화: (result/g)*x 순서
  // - 그래도 long 범위 초과 가능(문제의 입력 제약에 의존)
  public static long getLCM(int[] arr) {
    if (arr == null || arr.length == 0) return 0;

    long result = Math.abs((long) arr[0]);
    if (result == 0) return 0;

    for (int i = 1; i < arr.length; i++) {
      long x = Math.abs((long) arr[i]);
      if (x == 0) return 0;

      long g = getGCD(result, x);
      result = (result / g) * x;
    }
    return result;
  }
}

이제 이 유틸을 기준으로, 각 섹션에서 어떤 수식이 어떻게 구현되는지 살펴보겠습니다.

3. 소수 판별 isPrime: √n 경계, 최적화, i*i 오버플로우 방어

소수는 1과 자기 자신만을 약수로 가지는 자연수입니다. 코딩 테스트에서 소수 판별은 단독으로 나오기도 하지만, 소인수 분해의 전처리/검증 과정으로도 자주 등장합니다.

3-1. 왜 √n까지만 검사하면 충분한가?

합성수 n이 존재한다면 n = a × b로 표현됩니다. 이때 a와 b가 모두 √n보다 클 수는 없습니다(둘 다 크면 곱이 n을 초과). 따라서 2부터 √n까지만 나눠보면 소수 여부를 판정할 수 있습니다.

3-2. 홀수만 검사하는 이유

isPrime은 다음 최적화를 갖습니다.

• 2는 예외 처리
• 짝수는 즉시 탈락
• 이후는 홀수만 검사(i += 2)

이 구현은 단일 질의 기준으로 매우 실전적이며, 시간복잡도는 대략 O(√n)입니다.

3-3. 실전 함정: i*i 오버플로우

많은 코드가 루프 조건을 i * i <= n으로 작성합니다. 그런데 n이 int 최댓값 근처일 때 i가 커지면 i*i가 int 범위를 넘을 수 있어, 조건 판단이 깨질 수 있습니다. MathUtils는 이를 (long)i*i로 방어하여 유틸로서 안정성을 확보했습니다.

3-4. 소수 질의가 많다면? (체로 전환)

아래 문장이 보이면, isPrime을 수십만 번 반복 호출하는 방식은 위험합니다.

• “1부터 N까지 소수의 개수”
• “Q개의 질의마다 소수 여부를 답하라”

이 경우는 에라토스테네스의 체가 정답입니다. 유틸을 여러 개 두지 않기로 했으니 MathUtils에 넣지는 않더라도, 실전용 참고 코드로는 반드시 알고 있어야 합니다.

PrimeSieve.java (참고 코드)

import java.util.*;

public class PrimeSieve {

  // 0..n까지 소수 여부를 한 번에 계산
  public static boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    if (n >= 2) Arrays.fill(isPrime, true);
    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;

    for (int i = 2; (long) i * i <= n; i++) {
      if (!isPrime[i]) continue;

      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }

    return isPrime;
  }
}

4. 소인수 분해 getPrimeFactors(Map): 지수 맵으로 파생 수식 즉시 전개

소인수 분해는 “수를 분해해서 구조를 얻는 도구”입니다. 수 n을 다음 형태로 표현하면:

n = p1^a1 × p2^a2 × ... × pk^ak

여기서 (p, a) 정보만 있으면 코딩 테스트에서 자주 쓰는 파생 수식을 대부분 바로 계산할 수 있습니다. MathUtils가 Map<소수, 지수>를 반환하는 이유가 정확히 여기에 있습니다.

4-1. Trial Division 기반 소인수 분해의 실전 의미

getPrimeFactors는 2부터 시작해 i로 나누어 떨어지는 동안 반복해서 나누며 지수를 누적합니다. 핵심은 다음 두 가지입니다.

• while 루프로 “같은 소수 인수의 지수”를 한 번에 뽑는다.
• 루프가 끝난 뒤 n이 1보다 크면 남은 n은 마지막 소수 인수다.

시간복잡도는 최악에 가깝게 보면 O(√n)입니다. 하지만 실제로는 분해 과정에서 n이 계속 줄어들기 때문에 체감은 더 빠릅니다.

4-2. Map 반환이 코딩 테스트에서 유리한 이유

List로 소인수를 반환하면 예를 들어 360이 [2, 2, 2, 3, 3, 5]처럼 나오고, 이후 약수 개수/φ(n) 같은 공식에 쓰려면 다시 지수화해야 합니다. 반면 Map 반환은 처음부터 아래 형태로 줍니다.

{2=3, 3=2, 5=1}

즉, “파생 수식 계산을 위한 재가공 단계”가 제거되어, 코딩 테스트에서 중요한 빠른 구현에 유리합니다.

4-3. 예제: 소인수 지수 맵 출력

import java.util.*;

public class FactorPrintExample {

  public static void main(String[] args) {
    int n = 360;
    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);

    for (Map.Entry<Integer, Integer> e : exp.entrySet()) {
      System.out.println("prime=" + e.getKey() + ", exponent=" + e.getValue());
    }
  }
}

4-4. 약수의 개수: (a1+1)(a2+1)…

약수의 개수는 소인수 지수만 알면 끝납니다. n이 p1^a1 × ... × pk^ak이면 약수의 개수는 (a1+1)...(ak+1) 입니다.

DivisorCount.java

import java.util.*;

public class DivisorCount {

  public static long countDivisors(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);

    long count = 1;
    for (int e : exp.values()) {
      count *= (e + 1L);
    }
    return count;
  }
}

4-5. 제곱수 판정: 모든 지수가 짝수인가?

어떤 수가 완전제곱수라면, 소인수 분해의 모든 지수는 짝수입니다. Map 반환이면 판정이 매우 간단해집니다.

PerfectSquareCheck.java

import java.util.*;

public class PerfectSquareCheck {

  public static boolean isPerfectSquareByFactors(int n) {
    if (n < 0) return false;
    if (n == 0 || n == 1) return true;

    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);

    for (int e : exp.values()) {
      if ((e % 2) != 0) return false;
    }
    return true;
  }
}

4-6. 오일러 피 함수 φ(n): 서로소 개수의 핵심

φ(n)은 1부터 n까지 중 n과 서로소인 수의 개수입니다. 대표 공식은 다음입니다.

φ(n) = n × Π (1 - 1/p) (p는 n의 서로 다른 소인수)

Map 반환에서는 keySet이 이미 “서로 다른 소수 집합”이므로 별도의 Set 구성 없이 계산할 수 있습니다.

EulerPhi.java

import java.util.*;

public class EulerPhi {

  public static long phi(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);

    long result = n;
    for (int p : exp.keySet()) {
      result = result / p * (p - 1);
    }
    return result;
  }
}

4-7. 약수의 합: 등비수열 합의 곱

약수의 합은 각 소수 p에 대해 1 + p + p^2 + ... + p^a를 곱한 값입니다. 이 항은 등비수열 합이지만, 코딩 테스트에서는 입력 범위에 따라 오버플로우가 생길 수 있으니 연산 순서를 신중히 잡는 게 좋습니다.

SumOfDivisors.java

import java.util.*;

public class SumOfDivisors {

  public static long sumDivisors(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);

    long result = 1;
    for (Map.Entry<Integer, Integer> e : exp.entrySet()) {
      int p = e.getKey();
      int k = e.getValue();

      long term = 1;
      long pow = 1;
      for (int i = 0; i < k; i++) {
        pow *= p;
        term += pow;
      }

      result *= term;
    }
    return result;
  }
}

위 구현은 등비수열 공식보다 반복 곱으로 구성해 직관적이며, 작은 범위에서는 충분히 실전적입니다. 다만 n이 커서 약수의 합이 long을 넘을 수 있는 문제라면, 애초에 출력 타입이 BigInteger이거나 모듈러 연산이 붙는 경우가 많습니다(그때는 문제 조건에 맞춰 별도 전략을 선택해야 합니다).

5. 최대공약수 GCD: 유클리드 호제법, 배열 GCD, 약분/정규화

GCD는 코딩 테스트 수학의 가장 강력한 루틴입니다. “나누어 떨어짐”, “공통 단위”, “서로소”, “약분” 같은 표현이 보이면 거의 GCD로 수렴합니다.

5-1. 유클리드 호제법 핵심 등식

gcd(a, b) = gcd(b, a mod b)

나머지가 0이 될 때까지 반복하면 마지막 a가 최대공약수입니다. 이 알고리즘의 강점은 반복 횟수가 매우 적고, 실전에서 O(log n) 수준으로 빠르다는 점입니다.

5-2. 부호 정규화가 중요한 이유

수학적으로 gcd는 양수로 정의하는 경우가 일반적입니다. 코딩 테스트에서도 gcd 결과가 음수로 나오는 것을 기대하지 않습니다. 따라서 Math.abs로 입력을 정규화해 결과를 안정적으로 만들었습니다.

5-3. 분수 약분: GCD의 대표 사용처

분수 a/b를 기약분수로 만들려면 분자/분모를 gcd로 나누면 됩니다. 특히 큰 수 연산이 이어질 때, 먼저 약분을 해두면 중간 값 폭발을 줄일 수 있습니다.

FractionReduce.java

public class FractionReduce {

  public static long[] reduce(long numerator, long denominator) {
    if (denominator == 0) {
      throw new IllegalArgumentException("Denominator must not be zero"); // 분모는 0이면 안 됩니다.
    }

    long g = MathUtils.getGCD(numerator, denominator);
    return new long[] { numerator / g, denominator / g };
  }
}

5-4. 배열 GCD: folding 패턴

배열 GCD는 다음과 같은 누적 축약으로 구합니다.

gcd(a1, a2, ..., an) = gcd(...gcd(gcd(a1,a2),a3)...,an)

중간 결과가 1이면 더 줄어들 수 없으므로 조기 종료하는 것이 합리적입니다(여러 문제에서 체감 성능이 좋아집니다).

6. 최소공배수 LCM: 구현 순서, 오버플로우 감각, 배열 LCM

LCM은 “주기”를 다루는 도구입니다. “동시에”, “최초 공통 시점”, “공통 분모” 같은 단어가 나오면 LCM을 먼저 의심해도 좋습니다.

6-1. 수학 공식과 구현의 차이

수학 공식은 다음과 같습니다.

lcm(a, b) = |a × b| / gcd(a, b)

하지만 구현에서 그대로 a*b를 먼저 계산하면 중간 곱이 터질 수 있습니다. 그래서 MathUtils는 (a/gcd)*b 순서로 계산해 중간 값 폭발을 완화했습니다.

6-2. 배열 LCM이 위험한 이유

배열 LCM은 folding으로 구할 수 있지만, 원소들이 서로소에 가까우면 LCM이 곱에 가깝게 커집니다. 즉, long 범위를 빠르게 넘어갈 수 있습니다. 코딩 테스트에서는 보통 “결과가 long 안에 들어오도록” 제약을 주거나, “어떤 수로 나눈 나머지” 같은 형태로 바꾸어 냅니다. 이때는 문제 조건을 보고 전략을 바꿔야 합니다.

6-3. 오버플로우 감지(참고 코드)

일부 문제에서는 오버플로우를 직접 감지해야 할 수도 있습니다. MathUtils를 단순하게 유지하는 게 목표라면, 아래 로직을 “필요한 문제에서만” 참고 코드로 쓰는 방식이 현실적입니다.

public class LcmOverflowHint {

  public static long lcmWithCheck(long a, long b) {
    if (a == 0 || b == 0) return 0;

    a = Math.abs(a);
    b = Math.abs(b);

    long g = MathUtils.getGCD(a, b);
    long x = a / g;

    if (x != 0 && x > Long.MAX_VALUE / b) {
      throw new ArithmeticException("LCM overflow"); // LCM 계산 중 오버플로우
    }

    return x * b;
  }
}

7. 실전 응용 패턴 6선: 문제 문장을 수식으로 번역하는 법

이 섹션은 “이 유틸을 어디에 꽂는가?”를 패턴으로 정리합니다. 코딩 테스트는 결국 패턴 매칭입니다. 아래 6가지를 익히면 수학 문제의 체감 난도가 크게 떨어집니다.

패턴 1) 서로소 판정: gcd(a, b) == 1

public class CoprimeCheck {

  public static boolean isCoprime(int a, int b) {
    return MathUtils.getGCD(a, b) == 1;
  }
}

패턴 2) 분수 덧셈: 공통 분모(LCM) + 약분(GCD)

MathUtils는 int LCM만 제공하므로, 분모가 long 범위일 수 있는 문제에서는 아래처럼 같은 원리로 lcm을 계산해 사용합니다.

public class FractionAdd {

  // a/b + c/d 를 기약분수로 반환
  public static long[] add(long a, long b, long c, long d) {
    if (b == 0 || d == 0) {
      throw new IllegalArgumentException("Denominator must not be zero"); // 분모는 0이면 안 됩니다.
    }

    long g = MathUtils.getGCD(b, d);
    long lcm = (Math.abs(b) / g) * Math.abs(d);

    long x = a * (lcm / b);
    long y = c * (lcm / d);

    long numerator = x + y;
    long denominator = lcm;

    long gg = MathUtils.getGCD(numerator, denominator);
    return new long[] { numerator / gg, denominator / gg };
  }
}

패턴 3) 제곱수/거듭제곱 구조 판정: 지수 맵을 그대로 검사

소인수 지수 맵은 “수의 구조”를 직접 보여줍니다. 예를 들어 완전제곱수는 모든 지수가 짝수입니다. 이 패턴은 자주 나옵니다.

패턴 4) 주기 동기화: LCM으로 최초 공통 시점

public class CycleSync {

  public static long firstMeet(int cycleA, int cycleB) {
    return MathUtils.getLCM(cycleA, cycleB);
  }

  public static long firstMeetAll(int[] cycles) {
    return MathUtils.getLCM(cycles);
  }
}

패턴 5) 간격 통일: 인접 차이들의 GCD

좌표/시점 배열이 주어지고 “같은 간격으로 맞추기”류 문제는 인접 차이의 GCD로 떨어지는 경우가 많습니다.

import java.util.*;

public class GCDOfDifferences {

  public static int gcdOfSortedPositions(int[] pos) {
    Arrays.sort(pos);

    int g = 0;
    for (int i = 1; i < pos.length; i++) {
      int diff = pos[i] - pos[i - 1];
      g = MathUtils.getGCD(g, diff);
    }
    return Math.abs(g);
  }
}

패턴 6) “두 소수의 곱” 구조 판정: Map 크기와 지수로 끝내기

예를 들어 “서로 다른 두 소수의 곱(p ≠ q)”이라면, 소인수 종류가 2개이고 각 지수가 1이어야 합니다.

import java.util.*;

public class SemiprimeCheck {

  // n = p * q (p != q, p와 q는 소수)
  public static boolean isProductOfTwoDistinctPrimes(int n) {
    if (n < 0) return false;

    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);
    if (exp.size() != 2) return false;

    for (int e : exp.values()) {
      if (e != 1) return false;
    }
    return true;
  }

  // 참고: n이 "두 소수의 곱(같을 수도 있음)"인지 (정의에 따라 semiprime)
  public static boolean isSemiprimeAllowSame(int n) {
    if (n < 0) return false;

    Map<Integer, Integer> exp = MathUtils.getPrimeFactors(n);

    if (exp.size() == 1) {
      return exp.values().iterator().next() == 2; // p^2
    }

    if (exp.size() == 2) {
      for (int e : exp.values()) {
        if (e != 1) return false; // p^1 * q^1
      }
      return true;
    }

    return false;
  }
}

8. 요약: 언제 무엇을 꺼내 써야 할까?

마지막으로 문제 신호(키워드)와 메서드를 표로 정리합니다. 코딩 테스트에서는 “문장을 수식으로 번역”하는 속도가 곧 점수입니다.

문제 신호(키워드)	핵심 수식/개념	추천 메서드/패턴	주의점
소수인가?	√n까지 나눠보기	MathUtils.isPrime(n)	(long)i*i로 루프 조건 오버플로우 방어
약수 개수/합, 제곱수 판정, 수의 구조	소인수 지수 분해	MathUtils.getPrimeFactors(n) (Map 반환)	파생 수식은 long 범위 확인
서로소/약분/공통 단위	유클리드 호제법	MathUtils.getGCD(a,b), MathUtils.getGCD(long,long)	음수 입력도 양수 결과로 정규화
동시 주기/최소 공통 분모	lcm = |a/gcd| * |b|	MathUtils.getLCM(a,b), MathUtils.getLCM(arr)	배열 LCM은 long 초과 가능
간격 통일(좌표/시점), 등차 구조	차이들의 GCD	인접 차이를 구해 getGCD로 누적	정렬 후 차이를 쓰는 패턴이 많음
대량 소수 질의	에라토스테네스의 체	PrimeSieve.sieve(n) (참고 코드)	한 번 전처리 후 O(1) 질의

정리하자면, 코딩 테스트 수학은 “공식을 외우는 영역”이 아니라 자주 쓰는 수식 루틴을 빠르게 재사용하는 영역입니다. MathUtils는 특히 소인수 분해 결과를 Map으로 바꿔 “파생 수식 구현 속도”를 크게 끌어올렸습니다. 이제 남은 것은 문제 문장을 읽고, 어떤 메서드를 호출할지 자동으로 연결하는 연습입니다.