프로젝트 오일러 003

자연수 600851475143의 가장 큰 소인수를 구해야 합니다. 가장 큰 소인수를 알기 위해서는 소인수 분해를 해서 소인수의 목록을 찾고 그 중에서 가장 큰 수를 구하는 것이 가장 정석적인 방법일 것입니다. 문제에서 주어지는 수는 너무 크니까 조금 작은 728 정도의 수를 예로 들어서 생각해보겠습니다.

728은 2로 나누어집니다. 이를 식으로 나타내면 다음과 같고, 이 때 곱해지는 2와 364는 모두 728로 나눌 수 있으므로 둘 다 728의 인수입니다. 364는 2로 더 나눠볼 수도 있습니다. 2로 나눌 수 있을 때 계속 나눠보면 91이 남습니다. 이 때 91도 원래 수인 728의 인수입니다.

2로는 91을 나눌 수 없으니, 3, 5, 7 등의 수로 나누기를 시도해봅니다. 7은 91을 나눌 수 있고, 그 값은 13입니다. 이제 7과 13이 모두 728의 인수라는 사실을 알았습니다. 13은 7로 나눌 수 없고 7은 13의 제곱근보다 큽니다. 따라서 13을 나눌 수 있는 후보가 더 이상없으므로 728의 소인수 중에서 가장 큰 것은 13이되는 것입니다. 이런 계산 과정을 일반화하면 아래와 같습니다.

사실 이 과정은 소인수분해를 하는 과정과 완전히 동일하기는 합니다. 이 과정을 문제의 자연수에 대해서 시행하면 가장 큰 소인수를 알게 됩니다.

1. 2부터 시작해서 소수 (소수 목록을 모른다면 2, 3, 5, 7… 과 같은 홀수)로 나눠봅니다.
2. 나눌 수 있다면 반복해서 계속 나누고, 그 몫으로 원래의 수를 대신합니다.
3. 나누는 수는 점점 커지는데, 나누는 수가, 나눠지는 수의 제곱근보다 크다면 그 나눠지는 수는 소수이므로 가장 큰 소인수가 됩니다.

그리고 이제 이것을 파이썬 코드로 작성한다면 아래와 같이 작성하게 됩니다. 효율같은 건 생각하지 않고 나누는 수를 2부터 1씩 늘려갑니다.

s = 600851475143
i = 2
# 나누는 수가 나눠지는 수의 제곱근보다 크다면 나눠지는 수는 소수
while i <= s ** 0.5:
	if s % i == 0:
		s = s // i
	i += 1
print(s)