소수 판별과 약수 구하기

소수와 약수, 배수의 정의

소수는 영어로 prime 이라고 한다. 또한, $p$가 소수일 때 $p^k$를 prime power 라고 한다.

정수 $a, b$가 있을 때 $a$가 $b$의 약수라는 것은 정수 $n$이 있어 $b=an$이라는 것이다. 이때 $b$를 $a$의 배수라고 한다.

자연수 $p\geq2$의 약수가 $1$과 $p$ 뿐이면, $p$를 소수라고 부른다.

소수 판별 알고리즘

소수의 정의만 가지고 단순히 생각해 보자. 주어진 수 $N$을 $1$부터 $N$까지 나누어 보고, 나누어 떨어지는 수가 2개라면 소수이다.

다르게 말한다면, $N$을 $2$부터 $N-1$까지의 수로 나누어 봤을 때 나누어 떨어지는 경우가 있으면 소수가 아니고, 나누어 떨어지는 경우가 없으면 소수라는 것이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

위 코드는 주어진 수가 소수인지 판별하는 c++ 코드이다. 2부터 검사하기에, 1이 들어오는 경우를 예외처리 해 주어야 한다.

위 코드는 $2$부터 $N-1$ 까지의 모든 수를 계산해 본다. 따라서 시간복잡도는 $O(N)$이다.

소수 판별 알고리즘 최적화

합성수 $N$에서 $1$을 제외한 가장 작은 약수를 $d$라고 하자. $\frac{N}{d}$도 $1$이 아닌 $N$의 약수이므로, $d \leq\frac{N}{d}$ 이다. 우변의 $d$를 이항시키면 $d^2 \leq N$이고, 둘 다 자연수이므로 $d \leq \sqrt{N}$이다.

즉, 소수를 판별할 때 2부터 $\sqrt{N}$ 까지만 검사 해 주어도 충분하다.

반복문의 범위를 (int i = 2; i <= sqrt(n); i++)로 해도 괜찮지만, sqrt 함수는 실수연산이기에 오차가 발생할 수 있다. 따라서 for (int i = 2; i*i <= n; i++)으로 작성하는 것을 권장한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

위 코드의 시간복잡도는 $O(\sqrt{N})$이다.

소수 판별 예제 문제

약수 구하기 알고리즘

소수 판별 알고리즘을 조금만 응용하면 약수를 구할 수 있다.

$1$부터 $\sqrt{n}$까지 나누어 떨어질 때마다 벡터에 약수를 넣어 주면 된다.

자연수 $d$가 $n$의 약수라면, $n/d$ 역시 $n$의 약수라는 것을 잊지 말자. 이 때, $n=m^2$이 제곱수인 경우 $\sqrt{n}=m$이 약수로 두 번 세지는 경우를 조심하자.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            int d = n / i;
            if (i != d)
                v.push_back(d);
        }
    }
    
    sort(v.begin(), v.end());

    cout << n << "의 약수: ";
    for (int i : v) {
        cout << i << ' ';
    }
}

$O(\sqrt{N})$의 시간복잡도 내에 약수를 모두 구할 수 있다.

약수를 구한 이후 정렬을 해 주고 있다. STL 정렬의 시간복잡도가 $O(NlogN)$이라는 것은 모두 알고 있을 것이다.

long long 범위 내 약수의 개수의 상한선은 $\sqrt[3]{N}$개라고 어림짐작해볼 수 있다. 따라서 약수의 개수가 아무리 많아도 정렬에 쓰이는 시간복잡도는 $O(\sqrt[3]{N}log({\sqrt[3]{N}}))$이하이다.

양수 범위에서 $\sqrt[3]{N}log({\sqrt[3]{N}}) <\sqrt{N}$임이 자명하므로, 위 코드의 시간복잡도는 $O(\sqrt{N})$이다.

약수 구하기 알고리즘 최적화

위 코드를 조금만 개선하면 정렬을 할 필요가 없다.

v.push_back(d); 대신 다른 벡터에 담아둔 뒤, 역순으로 넣어주면 정렬된 약수를 구할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> divisor;
    vector<int> tmp;

    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisor.push_back(i);
            int d = n / i;
            if (i != d)
                tmp.push_back(d);
        }
    }

    divisor.insert(divisor.end(), tmp.rbegin(), tmp.rend());

    cout << n << "의 약수: ";
    for (int i : divisor) {
        cout << i << ' ';
    }
}

약수 구하기 예제 문제

범위 내 소수를 모두 구하는 알고리즘

기존 방법에서 반복문을 돌려 소수를 모두 찾으려 한다면, 범위가 조금만 커져도 시간초과가 뜰 것이다. 범위 내 소수를 모두 구해야 한다면, 에라토스테네스의 체를 활용하면 된다.

에라토스테네스의 체 알고리즘과 최적화에 대해서는 여기를 참고하고, 이번에는 간단하게 코드만 보고 넘어가자.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


vector<int> findPrime(int max) {
    vector<int> prime;
    vector<bool> check(max + 1, false);
    prime.push_back(2);
    for (int t = 3; t <= max; t += 2) {
        if (!check[t]) {
            prime.push_back(t);
            for (int i = t * t; i <= max; i += t) {
                check[i] = true;
            }
        }
    }
    return prime;
}

소인수 분해 알고리즘

여태까지 잘 따라왔다면, 소인수분해도 간단하게 할 수 있을 것이다. factorize 함수는 주어진 $N$을 효율적으로 소인수분해 하는 함수이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <iostream>
#include <vector>
#define ull unsigned long long
using namespace std;

vector<ull> factorize(ull n) {
    vector<ull> factors;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int main() {
    ull n;
    cin >> n;
    vector<ull> factors = factorize(n);
    cout << n << "의 소인수분해 : ";
    for (int i = 0; i < factors.size(); i++) {
        cout << factors[i] << ' ';
    }
    if (factors.size() == 1) {
        cout << "(소수)";
    }
}

번외 알고리즘

정수론 파트에는 어렵지만 재미있는 알고리즘들이 많다. 굳이 알 필요는 없지만, 번외로 준비해 봤다.

폴라드 로 소인수분해

int 범위 까지는 괜찮은데, long long 범위의 수를 위 소인수분해 알고리즘으로 계산하면 TLE가 난다.

이런 문제들은 범위가 $1 \leq N \leq 10^{18}$인데, 밀러-라빈 소수 판정법을 이용하여 폴라드 로 소인수분해 알고리즘을 구현하여 소인수분해한 후, DFS 등으로 약수를 구해주어야 한다.

나중에 시간이 되면 위 알고리즘도 다룰 예정이다.

소수 계량 함수

소수 계량 함수 $\pi(n)$은 $n$ 이하의 소수 개수를 나타내는 함수이다. 이 함수에 대해 다음 식이 성립한다.

$$\pi(n) \approx \frac{n}{\ln(n)}$$

예를 들어 $\pi(10^6)$의 근삿값은 $72382$고, 정확한 값은 $78498$이다.

이 함수를 이용하면 소수의 개수와 관련된 문제에서 시간복잡도를 간접적으로 구할 수 있다.