Python :: Project Euler 3번 문제 (코딩 문제 풀이)

안녕하세요.

이미 다 풀어두고 오랜만에 Project Euler 리뷰를 하게 되었습니다.

("블로그에 쓸게 없어서, 하나씩 올리는게 아닙니다."라고 하고 싶지만, 맞습니다.)

오늘의 문제는 소인수 분해에 대한 문제인데요. 먼저 아래의 문제를 읽고 코딩을 어떤 방향으로 진행할 것인지에 대해서 얘기하겠습니다.

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

위와 같은 부분에 대해서 문제 인식을 하기 전에 범위를 정해주는 것이 중요합니다. 그래서 무조건 숫자는 1부터 시작해야하며, 13195가 가장 마지막 숫자이기 때문에, 처음 숫자와 마지막 숫자의 변수가 각 a,b라고 지정한다면 아래와 같이 변수 설정을 먼저 해주는 것이 중요합니다.

a,b=1, 13195

또한, 두번째로는 시작 변수(a)는 마지막 숫자 변수(b) 이상이 될 수 없으며, 나누었을때 나머지가 0이 되어야하는 숫자만이 소인수가 될 수 있다는 것을 유의해야합니다. 그렇게 진행했을때 아래 코드에 따라서 제일 마지막에 나오는 소인수가 가장큰 소인수가 될 수 있다는 것을 알 수 있습니다.

a,b=1,600851475143

while a <b  :

if b%a==0 :

b=b/a

print(b)

a= a+1

위와 같이 진행한다면, 답은 아래와 같은 순서대로 나오게 됩니다.

이에 따라 가장 마지막에 나온 숫자가 소인수 중에 가장 큰 숫자가 되는 것을 알 수 있습니다.

600851475143.0

8462696833.0

10086647.0

6857.0

따라서 정답은 6857입니다.

위의 코드를 그냥 복사해서 붙여서 확인하시지 마시고, 중간 과정에 프린트 문으로 a,b 변수의 변화를 확인하시면서 진행하시면, 조금 더 이해하는데 도움이 될 것이라고 생각합니다.