프로젝트 오일러 003

어떤 큰 수의 가장 큰 소인수를 구해야합니다. 정석적인 방법은 소인수분해 함수를 구현하는 것이지만, 이 문제는 조금 더 간단한 방법으로 풀 수 있습니다.

문제에서 제시한 수보다 좀 작은 728을 예로 들어봅니다. 728은 (720 + 8)이므로 8의 배수라는 것을 알 수 있습니다. 즉 728은 2로 나누어지며, 3번을 나눌 수 있습니다. 2로 더 이상 나누어지지 않는다면 남은 91을 나눌 수 있는 다음으로 큰 수는 소수일 것으로 예상할 수 있습니다. 91의 제곱근은 9.#### 정도의 값일 것인데, 이 보다 작은 2, 5, 7 중에서 7로 나눠집니다. 7로 나눈 몫은 13입니다. 다시 13의 제곱근은 3.xxx 이고 이보다 작은 소수로는 더 이상 나눌 수 없으므로 13은 소수입니다. (물론 13은 잘 알려진 소수입니다만, 소수를 확인하기 위해서 이렇게 합니다.)

이런 계산 과정을 일반화하면 아래와 같습니다.

• $N=p\times q$ 일 때, p, q 는 모두 N의 약수(인수)입니다.
• 이 때 p, q 는 서로 같거나, 둘 중 하나가 더 작습니다.
• 만약 p == q 라면 p는 N의 제곱근입니다. 그리고 p < q 라면 p는 N의 제곱근보다 작습니다.

이 과정을 그대로 반복하면 아주 간단하게 풀 수 있는 문제입니다.

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

• 어떤 수를 소수로 나눌 수 없을 때까지 나누고 남은 몫은 나누는 소수보다 더 큰 소수에 의해서만 나눌 수 있습니다.
• 어떤 수의 제곱근보다 작은 수 중에서 나눌 수 있는 수가 없다면 그 수는 소수입니다.

이 두 가지 아이디어는 소인수 분해나 소수 판별에서 아주 중요하게 활용할 수 있는 사실이 됩니다.