약수 구하기 알고리즘 : n^0.5만 보고도 구할 수 있다.

 약수를 구하는 것은, 정수론 문제를 풀 때 기본이 되는 연산 중 하나입니다. 우리는 약수를 구하는 알고리즘을 다음과 같은 구현을 생각할 수 있을 겁니다.

 

 

 이것은 간단합니다. n의 약수를 구할 때, 나누는 수를 1부터 n까지 모두 검사해 봅니다. 만약에 n을 나누는 수 r로 나눴을 때, 나머지가 0이라면, r로 나누어 떨어지는 겁니다. 이것은 올바른 결과를 냅니다. 하지만, 오래 걸립니다. 예를 들어서, n의 값이 10^12만 되어도 아래와 같은 연산을 10^12번 해야 할 겁니다.

 

 

 10^12번. 상당히 끔찍하지 않나요? 1초에 단순 연산을 10^9회 정도 한다고 한다면, 1000초, 약 20초, 어마무시한 시간이 걸려버립니다. 이 끔찍한 시간을 줄일 수 있는 방법이 없을까요?

 

 

---

 Lemma 하나 들고 옵시다. 만약에, n이 합성수라면 반드시 sqrt(n) 이하의 수로 떨어진다. 그렇지 않다면, n은 소수이다. 1보다 큰 자연수 집합 N'에 대해서, 합성수 집합과 소수 집합은 다음과 같이 표현할 수 있어요.

 

 

 그러면 집합으로 표현하면 이런 관계일 겁니다. 일단, n이 합성수라고 하면, 1과 n 말고, n을 나누는 다른 수 a가 있다는 겁니다. 즉, 1<a<n을 만족합니다.

 

 

 그러면 aQ가 n일 겁니다. 그러면 3가지 부류로 나눠 봅시다. 먼저 a=Q인 경우입니다. 이 때에는 aQ = a^2 = N으로 쓸 수 있어요. 이 때 a의 값은 sqrt(N)이 됩니다. 나누는 수는 양수이기 때문입니다.

 

 

 다음에, a < Q인 경우는 어떨까요? 이 때에는 식을 조금 변형시켜야 하는데요. aQ>a^2일 겁니다. a>Q이기 때문입니다. aQ의 값이 N인데요. a^2<aQ<N이 성립합니다.

 

 

 N을 상수로 보고, a^2을 a에 대한 함수로 봅시다. a^2 = N이라는 건 결국 y = N과 y = x^2이 만나는 교점 아닌가요? 즉, 7호선 색 그래프하고, 3호선 색 그래프하고 만나는 지점이 2개 있는데, 각각 sqrt(N)과 -sqrt(N)입니다. a^2<N이려면 어떻게 되어야 하나요? a<sqrt(N)일 수 밖에 없어요. 그림을 보면요. 따라서, 이 경우에는, a가 sqrt(N)보다 작습니다.

 

 

 두 번째로 a>Q인 경우입니다. aQ = N이였네요. 그런데 a>Q이므로, Q^2보다 aQ가 큰 것은 자명합니다. 즉, Q^2 < aQ < N이 성립하는데요. 이 부등식을 풀면 Q<sqrt(N)이 됩니다. 즉, a가 Q보다 크면, Q가 sqrt(N)보다 작습니다. 세 경우를 모두 고려해 보아도, 나누어 지는 후보해들 중 최소 하나는, N^0.5보다 작거나 같을 수 밖에 없습니다.

 

 

---

 그러면 N이 소수라면 어떨까요? 이 경우에는 N을 나누는 수가 1과 N밖에 없는 경우입니다. 이 때에도, 사실 N^0.5까지만 보면 됩니다. 나누는 수를 N^0.5까지 증가시켰을 때도 나누어 지지 않는 경우, N은 1과 N으로만 나누어 집니다. 그렇지 않다고 해 볼까요? P일 경우에 Q라는 논리를 부정하면, P일 경우에, Q는 아니다입니다. 그러면 1과 N으로만 나누어 지지 않고 어떠한 특정한 수 a로 나누어 진다는 건데요. 단, 1<a<N입니다.

 

 

 그런데 N^0.5까지 봐도 나누어 떨어지지 않는다 했으니까, a > N^0.5라고 해 봅시다. 그러면 N을 a로 나누었을 때, 나머지가 0이고, 몫은 Q가 될 겁니다. 그러면, Q는 어떻게 되나요? Q가 N^0.5보다 커질 수 있나요? 만약에 그렇다고 하면, aQ의 값은 N보다 커져야 할 겁니다. 그런데 aQ의 값은 N입니다. 따라서, Q는 N^0.5보다 커질 수 없습니다.

 

 어? 그런데 Q가 N^0.5보다 작거나 같네요. 그런데, Q는 N을 나누었을 때 나머지가 0이 되게 하는 수 아닌가요? 전제에 모순입니다. 따라서, N이 소수라면 2부터 sqrt(N)까지만 보았을 때, 나누어 떨어지는 수가 없습니다.

 

 

 그래서 사실, 약수만 구한다고 한다면, 나누는 수의 제곱이 x보다 작거나 같을 때 까지만 검사하시면 됩니다. 예를 들어 n에다가 24를 넣었을 때, 이 프로그램이 출력하는 결과값은 아래 그림과 같습니다.

 

 

 그런데 이것을 오름차순으로 정렬하고 싶습니다. 그러면 어떻게 하면 좋을까요? 제일 간단한 방법은 다음과 같습니다.

 

 

 Java의 ArrayList라던지, C++의 vector와 같은 동적 배열에, 저장을 하는 겁니다. x의 약수를 구할 때, x가 i로 나누어 떨어진다면 x와 x/i를 같이 저장합니다. 그리고 정렬을 시킵니다. 중복을 처리하기 위해서, 정렬된 자료구조에서, 이전 것과 현재 것이 같으면, 출력을 하지 않으면 됩니다. 25를 넣었을 때 결과입니다.

 

 

 이렇게 했을 때, 시간 복잡도는 O(n)이 아닌, O(n^0.5)입니다.