01. 수학

1. 소수 판별 (Primality Test)

1.1 단일 수 판별

• 원리: 합성수 n의 약수는 반드시 루트 n 이하에 존재한다.
• 복잡도: O(sqrt(N))

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

1.2 에라토스테네스의 체 (범위 내 판별)

• 원리: 2부터 시작해 소수의 배수들을 소거하며 소수를 남기는 방식.
• 최적화: 내부 루프를 i*i에서 시작하여 중복 계산을 방지한다.

vector<int> sieve(int n) {
    vector<bool> state(n + 1, true);
    state[0] = state[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (!state[i]) continue;
        for (int j = i * i; j <= n; j += i) state[j] = false;
    }
    // state[i]가 true인 값들이 소수
}

2. 유클리드 호제법 (GCD & LCM)

• GCD (최대공약수): a % b 연산을 반복하여 나머지가 0이 될 때의 나누는 수.
• LCM (최소공배수): (a * b) / GCD 성질을 활용.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}