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

이번 포스팅에서는 프로젝트 오일러 3번 문제를 코드로 구현해보겠다.

 

문제는 아래와 같다.

 

600851475143의 소인수들 중 가장 큰 숫자를 구하시오.

 

구현한 코드는 아래와 같다.

 

import math

num_max = 600851475143
num_list = []
num_list_2 = []
num_list_odd = []

for i in range(0,math.floor(num_max**0.5)):
    if num_max%(i+1)==0:
        num_list.append(i+1)

for i in num_list:
    num_list_2.append(num_max/i)

num_list_2.reverse()
num_list.extend(num_list_2)

for i in num_list:
    if i%2!=0:
        num_list_odd.append(i)
        for j in range(2,math.floor(i**0.5)):
            if i%j==0:
                num_list_odd.remove(i)
                break

print(num_list)
print(num_list_odd)
print(max(num_list_odd))

위 코드는 우선 600851475143 의 약수를 모두 구한 뒤, 다시 각 약수들이 소수인지 확인하는 방식의 코드이다.

 

약수를 구하는 과정에서는 주어진 숫자의 루트 제곱근까지만 for문을 실행했으며, 1에서부터 차례대로 일일이 계산하였다.

 

구한 약수들은 num_list 라는 배열에 저장하였다.

 

약수들을 모두 구한 뒤, 다시 각 약수들에 대하여 소수가 아닌 숫자를 리스트에서 제외하는 방식으로 소수를 구하였다.

 

최종적으로 가장 큰 수를 print 하였다.

 

결과는 아래와 같이 나오게 된다.

 

첫번째 줄은 주어진 숫자의 약수를 모두 표시한 것이며, 두 번째 줄이 해당 약수들 중 소수인 수만 표시한 것이다.

 

마지막으로 6857이 주어진 600851475143의 약수 중 가장 큰 숫자이다.

 

하지만 위 코드는 굉장히 비효율적인 로직을 가진 코드이다.

 

약수를 일일이 다 구하고, 해당 약수들을 다시 일일이 소수인지 확인하기 때문이다.

 

다음 포스팅에서는 보다 효율적이지만 동일한 결과를 뽑아낼 수 있는 코드를 구현해보도록 하겠다.