[Python][Projet Euler] 가장 큰 소인수 구하기 - 003

소인수를 구하는 다양한 방법이 있지만 효율적인 알고리즘을 위해서라면

O(n) 시간 안에 구하는 것이 최적인 것 같다.

에라토스테네스 체에서 영감을 얻어 나누어 떨어질때 수를 나누어주면 해결될 것 같다.

 

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

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

num = 600851475143

denom = 2
target = []
while num > 0:
    if num % denom == 0:
        num /= denom
        target.append(denom)
    elif num == 1:
        break
    else:
        denom += 1

print(max(target))