Python 예제 - 프로젝트 오일러 3번 문제 (가장 큰 소인수 찾기) 2

이번 포스팅에서는 저번에 구현하였던 프로젝트 오일러 3번 문제의 다른 구현 방법을 사용해보도록 하겠다.

 

저번 포스팅에서는 주어진 숫자의 모든 약수를 다 구한 뒤, 각각의 약수가 소수인지 일일이 확인하는 방식을 사용하였다.

 

하지만 이와 같은 방식은 너무 많은 계산양을 필요로 하기 때문에, 이번 포스팅에서는 조금 다른 방법으로 코드를 구현해보려 한다.

 

우선 코드는 아래와 같다.

 

num_max = 600851475143
i = 2

while num_max > 1:
    if num_max%i==0:
        num_max /= i
    elif num_max==1:
        break
    else:
        i += 1

print(i)

위 코드를 보면 양이 획기적으로 줄어든 것을 볼 수 있다.

 

먼저 주어진 숫자(num_max)를 2부터 1씩 증가시키면서 차례로 나눈다.

 

중간에 나누어 떨어지는 경우가 발생하면, num_max 값을 그 몫으로 대체한다.

 

이와 같은 계산을 반복하다가 num_max가 1이 되면 루프를 빠져나온다.

 

이때 i 값이 문제에서 구하고자 하는 가장 큰 소인수임을 알 수 있다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

이해가 잘 되지 않을 수 있으니 조금 작은 숫자로 위 코드의 흐름을 파악해보도록 하자.

 

num_max = 10

i = 2

 

[loop 1]

num_max = 10/2 = 5

i = 2

 

[loop 2]

num_max = 5

i = 3

 

[loop 3]

num_max = 5

i = 4

 

[loop 4]

num_max = 5

i = 5

 

[loop 5]

num_max = 1

break!

 

결과적으로 마지막 i 값인 5가 10의 가장 큰 소인수가 되는 것을 볼 수 있다.