[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

학원 학생들이 약수를 모두 찾는 (또는 약수의 합, 개수를 구하거나, 소수 판별 등등) 코드를 어떻게 짜는지 살펴보면, 백이면 백 \(O(n)\) 알고리즘을 사용한다. 하지만 어떤 수의 모든 약수를 구하는 일은 \(O(\sqrt n)\) 시간만에 할 수 있다. 대부분의 사람들이 이 사실을 모르거나 알더라도 적극적으로 이용하지 않는 것 같아 적어본다.

우선 다음 두 정리를 살펴보자. 약수랑 제곱근이 뭔지만 안다면, 직관적으로 "그렇겠구나" 정도는 생각할 수 있는 것들이다.
1. 자연수 \(d\)가 자연수 \(n\)의 약수이면, \(n/d\)도 \(n\)의 약수이다.
2. 양수 \(d\)와 \(n\)에 대해 \(d\le\sqrt n \Longleftrightarrow n/d\ge\sqrt n\).
1 증명) 자연수 \(d\)가 자연수 \(n\)의 약수이면 \(qd=n\)을 만족하는 자연수 \(q\)가 존재하고, 약수의 정의에 의해 \(q\)도 \(n\)의 약수이다. 그리고 \(q=n/d\)이다. 따라서 \(n/d\)도 \(n\)의 약수이다.
2 증명) \(d\le\sqrt n\)의 양변에 \(\sqrt n / d\)를 곱하면 된다.

이를 통해 다음 정리도 증명할 수 있다.
자연수 \(n\)의 약수의 개수를 \(k\)라 하고, \(n\)의 약수들 중에서 \(i\)번째로 작은 것을 \(d_i\)라 하면 다음이 모두 성립한다.
3. \(d_i=n/d_{k+1-i}\)이다. 쉽게 말해, \(n\)의 \(i\)번째로 작은 약수는 \(n\)을 \(n\)의 \(i\)번째로 큰 약수로 나눈 것과 같다.
4. \(i\le\lceil k/2\rceil \Longleftrightarrow d_i\le \sqrt{n}\).
3 증명) \( \{n/d_i|i=1,\cdots,k \} = \{ d_i|i=1,\cdots,k \} \)임은 위의 정리 1로 쉽게 보일 수 있다. 또, \(n/d_k<n/d_{k-1}<\cdots<n/d_1\)이므로 증명이 된다.
4 증명) 위의 정리 2에 의해, \(d_i\le \sqrt{n}\)을 만족하는 \(d_i\)의 개수와 \(d_i\ge \sqrt{n}\)을 만족하는 \(d_i\)의 개수가 같아야 한다. 만약 \(n\)이 제곱수이면 \(d_{\lceil k/2\rceil}=\sqrt n\)이고, 제곱수가 아니라면 \(d_{\lceil k/2\rceil}<\sqrt n<d_{\lceil k/2\rceil+1}\)이므로, 항상 \(i\le\lceil k/2\rceil \Longleftrightarrow d_i\le \sqrt{n}\)이다.

수학적으로 막 적어보았지만, 중요한 것은 결론이다. 바로 \(n\)의 약수들 중 \(\sqrt n\) 이하인 것들만 구하면, 나머지는 \(n\)을 그것들로 나눠 구할 수 있다는 것이다.

예를 들어 루트 126은 11보다 크고 12보다 작다. 그리고 126의 약수들 중 11 이하인 것은 1, 2, 3, 6, 7, 9이다. 그러므로 나머지 약수들은 126을 1, 2, 3, 6, 7, 9로 나눈 126, 63, 42, 21, 18, 14이고, 더이상은 없다.

따라서 예를 들어 n의 약수의 합을 구하는 프로그램은 다음과 같이 \(O(\sqrt n)\) 시간복잡도로 작성할 수 있다. 루트를 직접 구하지 않고 i * i <= n 조건을 사용한 점에 주목하자. 또, i가 정확이 루트 n일 때는 i와 n/i가 같은 값이므로, 한 번만 더해주기 위해 따로 처리해 주었다. (다만 프로그램 성능 상으로는 제곱수인 경우의 처리는 루프 바깥에서 따로 해주는 게 빠를 것 같다...)

int sumOfDivisors(int n) {
    int sum = 0;
    for (int i = 1; i * i <= n; i++) {
        if (i * i == n) {
            sum += i;
        }
        else if (n % i == 0) {
            sum += i + n / i;
        }
    }
    return sum;
}

 

또, 소수 판별은 다음과 같이 해줄 수 있다. 1로는 나눠볼 필요가 없다는 점, 그리고 1은 소수가 아니라는 점에 주의하자. (n==1일 경우를 따로 처리해주지 않으면, for문 안으로 안 들어가기 때문에 true가 리턴된다.)

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;
}

 

물론 여러 수에 대해 소수 판별을 하는 경우에는 보통 에라토스테네스의 체를 사용하는 것이 훨씬 빠르다.