프로젝트 오일러 003

문제

3번 문제

가장 큰 소인수 구하기

사이냅소프트

이번 문제는 '어떤 수의 가장 큰 소인수'를 구하는 문제입니다. 문제에서 가장 큰 소인수를 구하라고 했기 때문에, 소인수 분해를 구현하면 '됩니다'. 된다고 했지 그것만이 정답인 것은 아닙니다. 물론 프로젝트 오일러의 다른 문제들을 풀기 위해서는 소인수 분해를 (그것도 썩 괜찮은 성능의) 구현하긴 해야합니다. 하지만 이 문제는 소인수분해를 구현하지는 않고 같은 원리로 답만 구해보도록 하겠습니다.

인수

소인수는 소수(prime number)인 인수이기 때문에, 우선 인수가 뭔지를 알아야합니다. 어떤 하나의 정수나 다항식을 다른 몇 개의 정수나 다항식의 곱으로 표현할 때, 곱해지는 정수나 다항식을 본래 정수나 다항식의 인수라고 합니다. 정수의 범위에서 인수는 약수와 같은 개념입니다.

하나의 정수를 다른 두 수의 곱으로 표현하는 방법은 수에 따라 여러 가지가 될 수 있습니다. '16 = 2 x 8 = 4 x 4' 와 같이 말이죠. 하나의 수를 두 개의 인수의 곱으로 표현할 때, 이 두 인수에 대해서는 다음과 같은 사실을 말할 수 있습니다.

• N = p * q 일 때, p, q 중에서 하나는 다른 한 수보다 크거나 같습니다. (당연한 이야기죠)
• p < q 라면, p는 N의 제곱근보다 작거나 같습니다.

풀이

원래 문제보다 좀 더 간단한 문제를 만들어 봅시다. 728을 예로 들어보겠습니다. 728은 8의 배수입니다. 728 = 8 * 91 이며, 이 때 8은 2의 세제곱입니다. 728을 2로 나눌 수 없을 때 까지 나누어 91이 되면, 3으로 나누어 봅니다. 3으로 나누어지지 않으면 4로 나누어봅니다. 그런데 2로 더 이상 나눌 수 없을 때까지 나눈 결과가 91이므로, 이 값은 4나 8, 16과 같은 2의 배수로는 더 이상 나누어 지지 않음이 확실합니다. 따라서 91을 나눌 수 있는 가능성이 있는 수들은 모두 소수일 것입니다.

91을 나눌 수 있는 수를 찾기 위해서는 3~91까지의 수를 모두 시험해봐야 하는 것은 아닙니다. 위의 두 번째 사실(두 인수 중 작은 수는 본래 수의 제곱근보다 작다)에 의해 그 다음번 인수는 91의 제곱근 (약 9.53) 보다 작아야 합니다. 7이 91을 나눌 수 있는 수 이죠. 그 몫은 13이고 이는 한 눈에 소수라는 것을 알 수 있지만, 7보다 큰 자연수 중에는 13을 나눌 수 있는 자연수가 없습니다. (애초에 13의 제곱근보다 7이 큽니다.) 따라서 가장 큰 소인수는 13입니다.

이런 식으로 본래 수를 작은 인수로부터 나누어나가면, 결국 더 이상 나눌 수 있는 값이 없다면 가장 큰 소인수가 남은 것이 됩니다. 지금까지의 내용을 코드로 정리하면 다음과 같습니다.

s = 600851475143
i = 2
while i <= s ** 0.5:
    if s % i == 0:
        s //= i
    i += 1
print(s)