[Algorithm] 정수론

소수

• 소수(prime number): 양의 약수가 1과 자기 자신 두 개 뿐인 자연수
  • 1은 소수도 아니고 합성수도 아님 => 예외 처리 필요!

가장 단순한 소수 판별 방법

• n이 주어졌을 때, 2 ~ n-1까지 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인
• 최적화 포인트: 합성수 n이 p * q로 표현될 때, 한 수는 항상 sqrt(n) 이하, 다른 한 수는 항상 sqrt(n) 이상이다.
  • => n-1까지 순회하지 않고 sqrt(n)까지만 순회하도록 최적화 가능
• 입력의 개수가 작은 경우에만 사용 가능 (32비트 정수)

public static boolean isPrime(int n) {
    // 맨 처음에 1 이하의 수와 2를 예외 처리
    if (n <= 1) return false; 
    if (n == 2) return true;
    // 짝수들 예외 처리
    if (n % 2 == 0) return false;

    int sqrtN = (int) Math.sqrt(n);
    // 홀수들만 확인하면 ok
    for (int i = 3; i < sqrtN; i += 2) {
        if (n % i == 0) return false;
    }

    return true;
}

많은 수에 대해 소수 판단을 해야 하는 경우?

=> 에라토스테네스의 체를 이용하여 특정 범위의 숫자들에 대해 미리 소수 판단을 해 두는 방법 사용

소인수 분해(prime factorization)

• 소인수 분해: 한 합성수를 소수들의 곱으로 표현하는 방법을 찾는 방법
• [2, sqrt(n)] 범위에서 n의 소인수가 될 수 있는 수들을 하나하나 순회하면서, n의 약수를 찾을 때마다 n을 이 숫자로 나눔
• 시간복잡도: O(n^1/2)

public static List<Integer> getFactorSimple(int n) {
    List<Integer> factors = new ArrayList<>();

    int sqrtN = (int) Math.sqrt(n);
    for (int div = 2; div < sqrtN; div++) {
        while (n % div == 0) {
            factors.add(div);
            n /= div;
        }
    }

    if (n > 1) factors.add(n);

    return factors;
}

에라토스테네스의 체(Sieve of Eratosthenes)

• 에라토스테네스의 체: 주어진 수 n 이하의 소수들을 모두 찾아내는 방법
  • 간단한 소수 판별 알고리즘을 [2, n] 범위의 모든 자연수에 대해 확장한 것
• 시간 복잡도는 거의 O(n)과 비슷
• 문제점: 메모리 사용량이 큼
  • 짝수를 별도로 처리해서 필요한 배열의 크기를 절반으로 줄이거나,
  • 비트마스크를 이용하는 등의 기법을 통해 체가 사용하는 메모리의 양을 최적화 가능

class Eratosthenes {
    static boolean[] isPrime;

    // n 이하의 소수들을 모두 찾기
    public static void eratosthenes(int n) {
        isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = isPrime[1] = false;
        int sqrtN = (int) Math.sqrt(n);

        for (int i = 2; i < sqrtN; i++) { // 최적화 포인트 1
            // 이미 지워졌다면(이미 소수가 아님이 밝혀졌다면)
            if (!isPrime[i]) continue;

            for (int j = i * i; j <= n; j += i) { // 최적화 포인트 2
                isPrime[j] = false;
            }
        }
    }
}

• 각 수가 지워졌는지 여부를 불린 값 배열(isPrime[])에 저장
  • isPrime[i] == true라면 소수임
• 최적화 포인트
  1. n까지 찾는 것이 아니라 sqrt(n)까지만 찾음
  2. i의 배수들을 모두 지울 때 2 * i에서 시작하는 것이 아니라, i * i에서 시작

에라토스테네스의 체를 이용한 빠른 소인수 분해

• 정해진 범위의 수들에 대해 소인수 분해를 여러 번 해야한다면? -> 에라토스테네스의 체를 응용해 훨씬 빠르게 소인수 분해 수행 가능
• 최적화 비결: 체에서 각 숫자의 가장 작은 소인수를 기록하기

class Erathosthenes {

    // minFactor[i] = i의 가장 작은 소인수(i가 소수인 경우 자기 자신)
    static int[] minFactor;

    public static void eratosthenes2(int n) {
        minFactor = new int[n + 1];
        // 0과 1은 예외 처리
        minFactor[0] = minFactor[1] = -1;

           // 모든 숫자를 처음에는 소수로 표시
        for (int i = 2; i <= n; i++) {
            minFactor[i] = i;
        }

        int sqrtN = (int) Math.sqrt(n);
        for (int i = 2; i < sqrtN; i++) {
            if (minFactor[i] != i) continue;

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

    public static List<Integer> getFactor(int n) {
        List<Integer> factors = new ArrayList<>();
        // n이 1이 될 때까지 가장 작은 소인수로 나누기를 반복
        while (n > 1) {
            factors.add(minFactor[n]);
            n /= minFactor[n];
        }

        return factors;
    }
}

---

유클리드 알고리즘(Euclidean Algorithm)

• 유클리드 알고리즘: 두 수의 최대공약수를 구하는 방법
  • 두수 p, q(p > q)의 공약수의 집합은 p-q, q의 공약수 집합과 같다는 점을 이용
  • => gcd(p, q) == gcd(p-q, q)
• 여기까지만 하면, 숫자가 큰 경우 많은 재귀 호출이 생기므로 이를 최적화 하기 위해 p-q 대신 p%q를 취하기

public class GCD {

    // gcd(p, q) == gcd(p-q, q) 이용
    public static int gcdSimple(int p, int q) {
        if (p < q) {
            int tmp = p;
            p = q;
            q = tmp;
        }

        if (q == 0) return p;
        return gcdSimple(p - q, q);
    }

    // 최적화 적용
    public static int gcd(int p, int q) {
        if (q == 0) return p;
        return gcd(q, p % q);
    }

    public static void main(String[] args) {
        System.out.println(gcdSimple(1023, 6));
        System.out.println(gcd(1023, 6));
    }
}

---

모듈러(modulus) 연산

• 모듈러 연산: 모듈로 M에 도달하면 다시 0으로 돌아가는 정수들을 가지고 하는 연산
• 모듈러 연산에서 모든 정수는 M으로 나눈 나머지로 표현됨
• 모듈러 연산은 무한히 큰 정수를 다룰 수 없는 컴퓨터의 특성 때문에 프로그램이 대회에 종종 출현

모듈러 덧셈, 뺄셈, 그리고 곱셈

• 두 수를 더한 뒤 나머지를 취하는 것은 미리 두 수의 나머지를 구한 뒤 더하고, 다시 나머지를 취하는 것과 동일
• 뺄셈 & 곱셈에도 동일한 논리 적용 가능
• (a+b)%M = ((a%M) + (b%M)) % M
• (a-b)%M = ((a%M) - (b%M)) % M
• (a*b)%M = ((a%M) * (b%M)) % M

public class ModulaPractice {
    public static void main(String[] args) {
        int a = 51235;
        int b = 5416;
        int M = 37;
        // (a+b)%M = ((a%M) + (b%M)) % M
        System.out.println((a + b) % M);
        System.out.println((a % M + b % M) % M);

        // (a-b)%M = ((a%M) - (b%M)) % M
        System.out.println((a - b) % M);
        System.out.println((a % M - b % M) % M);

        // (a*b)%M = ((a%M) * (b%M)) % M
        System.out.println((a * b) % M);
        System.out.println((a % M * b % M) % M);
    }
}