소수 판정과 소인수분해(Primality Test/Factorization)

소수(Prime number)는 $1$과 자기 자신을 제외한 양의 정수로는 나누어 떨어지지 않는 $1$이 아닌 양의 정수를 의미한다. 소수가 아닌 수를 합성수라고 한다. $1$은 소수도 합성수도 아니다.

 

소수에는 여러 흥미로운 성질이 있다. 그 중에서 소수 판정과 소인수분해에 쓰이는 중요한 성질로 어떤 합성수 $n$에 대해 $1$이 아닌 $n$의 약수 중 적어도 하나는 $\sqrt{n}$보다 작다는 성질이 있다.

---

소수 판정

소수 판정(Primality Test)는 어떤 수 $n$이 소수인지 아닌지를 판단하는 문제로, 정수론에서 중요한 문제 중 하나다. 어떤 수 $n$이 소수이려면 $2 \leq k \leq n-1$인 정수 $k$로 나누어 떨어지지 않아야 하므로, $2$부터 $n-1$까지 나눠보면 소수인지 판별할 수 있다. 이 경우에 시간 복잡도는 $O(n)$이 된다.

bool isPrime(int n) {
    if (n < 2) return 0; // 2보다 작으면 무조건 소수가 아님
    if (n == 2) return 1; // 2는 소수

    for (int i = 2; i < n; i++) {
        if (n % i == 0) return 0; // 나누어 떨어지면 소수가 아님
    }

    return 1;
}

 

여기에서 "어떤 합성수 $n$에 대해 $1$이 아닌 $n$의 약수 중 적어도 하나는 $\sqrt{n}$보다 작다"라는 성질을 이용하면 $n-1$까지가 아니라, $\sqrt{n}$보다 작은 수로만 나누어 보면 된다. 시간 복잡도는 $O(\sqrt{n})$이다.

bool isPrime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;

    for (int i = 2; i*i <= n; i++) { // i*i <= n까지만 나누기
        if (n % i == 0) return 0;
    }

    return 1;
}

---

소인수분해

소인수분해(Prime Factorization)은 어떤 양의 정수 $n$을 소수들만의 곱으로 나타내는 것이다.

 

소인수분해를 하는 간단한 방법은 역시 $\sqrt{n}$까지의 수들로 모두 나누는 것이다. 이 때, 약수가 소수인지 따로 판별할 필요가 없는데 그 이유는 합성수인 약수가 있다면 그 합성수의 약수인 소수들로 이미 모두 나누었기 때문에 결국 합성수로 나누게 되는 경우는 존재하지 않기 때문이다. 시간 복잡도는 $O(\sqrt{n})$이다.

vector<int> factorize(int n) {
    vector<int> ret;

    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                ret.push_back(i);
                n /= i;
            }
        }
    }

    if (n > 1) ret.push_back(n);
    return ret;
}