Theme:

수학 기초 — 소수 판별, GCD, 모듈러 연산이 쓰이는 곳

알고리즘수학
2025-09-20·7 min read

알고리즘 문제를 풀다 보면 갑자기 수학이 등장합니다. 소수, 최대공약수, 나머지 연산... 왜 이런 게 코딩에서 필요한 걸까요?

소수 판별

소수(Prime Number)는 1과 자기 자신만으로 나누어지는 2 이상의 자연수입니다. 2, 3, 5, 7, 11, ...

기본 판별법 — O(√n)

n이 소수가 아니라면, √n 이하의 약수가 반드시 존재합니다.

JAVA
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; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

에라토스테네스의 체 — O(n log log n)

범위 내의 모든 소수를 한 번에 구할 때 사용합니다. 소수의 배수를 차례로 지워나가는 방식입니다.

JAVA
public static boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            // i의 배수를 모두 소수가 아닌 것으로 표시
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

j = i * i부터 시작하는 이유는 i * 2, i * 3, ... i * (i-1)은 이전 단계에서 이미 처리되었기 때문입니다.

소수가 쓰이는 곳

  • **해시 테이블 **: 버킷 크기를 소수로 하면 해시 충돌이 줄어듭니다.
  • ** 암호화(RSA)**: 매우 큰 두 소수의 곱으로 키를 생성합니다.
  • ** 난수 생성 **: 선형 합동 생성기에서 소수 모듈러를 사용합니다.

최대공약수(GCD)와 최소공배수(LCM)

유클리드 알고리즘 — O(log(min(a, b)))

두 수의 최대공약수를 구하는 가장 효율적인 방법입니다.

** 핵심 원리 **: GCD(a, b) = GCD(b, a % b), b = 0이면 a가 GCD.

JAVA
// 재귀 버전
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 반복문 버전
public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

최소공배수

JAVA
public static int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 오버플로우 방지를 위해 나누기를 먼저
}

확장 유클리드 알고리즘

ax + by = GCD(a, b)를 만족하는 x, y를 구합니다. 모듈러 역원을 구할 때 사용됩니다.

JAVA
// result[0] = gcd, result[1] = x, result[2] = y
public static int[] extendedGcd(int a, int b) {
    if (b == 0) return new int[]{a, 1, 0};

    int[] result = extendedGcd(b, a % b);
    int gcd = result[0];
    int x = result[2];
    int y = result[1] - (a / b) * result[2];

    return new int[]{gcd, x, y};
}

모듈러 연산

큰 수의 연산에서 오버플로우를 방지하기 위해, 또는 결과를 특정 범위로 제한하기 위해 나머지 연산을 사용합니다.

기본 성질

PLAINTEXT
(a + b) % m = ((a % m) + (b % m)) % m
(a × b) % m = ((a % m) × (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m  // 음수 방지를 위해 +m

**주의 **: 나눗셈에는 이 법칙이 직접 적용되지 않습니다.

큰 수의 거듭제곱 (모듈러 거듭제곱)

JAVA
// a^b mod m을 O(log b)에 계산
public static long modPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;

    while (exp > 0) {
        if ((exp & 1) == 1) {  // exp가 홀수이면
            result = (result * base) % mod;
        }
        exp >>= 1;           // exp를 2로 나눔
        base = (base * base) % mod;
    }
    return result;
}

모듈러 역원

a / b mod m을 계산하려면, b의 모듈러 역원 b^(-1)을 구해서 a × b^(-1) mod m으로 바꿉니다.

페르마의 소정리에 의해, m이 소수이면 b^(-1) ≡ b^(m-2) (mod m).

JAVA
// m이 소수일 때 b의 모듈러 역원
public static long modInverse(long b, long m) {
    return modPow(b, m - 2, m);
}

조합론(Combinatorics)

알고리즘 문제에서 경우의 수를 셀 때 조합 공식이 필요합니다.

이항 계수 (nCr)

JAVA
// DP로 이항 계수 계산 (파스칼의 삼각형)
public static long[][] binomial(int n, long mod) {
    long[][] dp = new long[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;
        }
    }
    return dp;
}

// 팩토리얼 + 모듈러 역원으로 계산 (n이 큰 경우)
public static long nCr(int n, int r, long mod) {
    if (r > n) return 0;
    long[] fact = new long[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i-1] * i % mod;
    }
    return fact[n] % mod
         * modInverse(fact[r], mod) % mod
         * modInverse(fact[n - r], mod) % mod;
}

실무에서 쓰이는 수학

해시 함수와 소수

해시 테이블의 크기를 소수로 설정하면, 입력 패턴에 관계없이 해시값이 고르게 분포됩니다.

JAVA
// 문자열 해시 (다항 해시)
public static int polynomialHash(String s, int mod) {
    int hash = 0;
    int base = 31; // 소수 사용
    for (char c : s.toCharArray()) {
        hash = (hash * base + c) % mod;
    }
    return hash;
}

분산 시스템의 Consistent Hashing

서버 노드를 해시 링에 배치할 때, 해시 함수의 균등 분포가 중요합니다. 이때도 모듈러 연산이 핵심입니다.

체크섬과 검증

TCP 체크섬, CRC 등에서 모듈러 연산이 사용됩니다.

페이지네이션 계산

JAVA
// 전체 count에서 필요한 페이지 수 계산
int totalPages = (totalCount + pageSize - 1) / pageSize;
// 이것도 나눗셈의 올림인데, 수학적으로는 ⌈totalCount / pageSize⌉

주의할 점

모듈러 연산에서 나눗셈을 직접 적용하는 실수

(a / b) % m은 (a % m) / (b % m) % m이 아닙니다. 나눗셈에는 모듈러 역원이 필요합니다. 이를 모르면 결과가 완전히 달라집니다.

LCM 계산에서 오버플로우

a * b / gcd(a, b) 순서로 계산하면 a * b에서 int 오버플로우가 발생할 수 있습니다. 반드시 a / gcd(a, b) * b 순서로 나누기를 먼저 해야 합니다.

에라토스테네스의 체에서 j = i*2부터 시작하는 비효율

j = i * i부터 시작해야 합니다. i * 2, i * 3 ... i * (i-1)은 이전 단계에서 이미 처리되었기 때문입니다.

정리

개념핵심 알고리즘시간 복잡도실무 활용
소수 판별에라토스테네스의 체O(n log log n)해시, 암호화
GCD유클리드 알고리즘O(log n)분수 약분, 스케줄링
모듈러 연산빠른 거듭제곱O(log n)오버플로우 방지, 해시
조합파스칼/팩토리얼O(n) 전처리경우의 수 계산

기억할 포인트:

  • 소수 판별은 √n까지만 확인하면 됩니다. 범위 전체라면 에라토스테네스의 체를 사용하세요.
  • 유클리드 알고리즘은 GCD(a, b) = GCD(b, a % b)가 전부입니다.
  • 모듈러 연산은 덧셈과 곱셈에 분배 법칙이 성립하지만, 나눗셈에는 모듈러 역원이 필요합니다.
  • 해시 함수에서 소수를 사용하는 이유를 이해하면, HashMap의 동작 원리도 더 깊이 이해할 수 있습니다.
related posts
댓글 로딩 중...
On This Page
소수 판별기본 판별법 — O(√n)에라토스테네스의 체 — O(n log log n)소수가 쓰이는 곳최대공약수(GCD)와 최소공배수(LCM)유클리드 알고리즘 — O(log(min(a, b)))최소공배수확장 유클리드 알고리즘모듈러 연산기본 성질큰 수의 거듭제곱 (모듈러 거듭제곱)모듈러 역원조합론(Combinatorics)이항 계수 (nCr)실무에서 쓰이는 수학해시 함수와 소수분산 시스템의 Consistent Hashing체크섬과 검증페이지네이션 계산주의할 점모듈러 연산에서 나눗셈을 직접 적용하는 실수LCM 계산에서 오버플로우에라토스테네스의 체에서 j = i*2부터 시작하는 비효율정리