[파이썬]프로젝트 오일러 #3

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

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

n = 600851475143
prime = []
i = 2

while n>=i: #마지막으로  나눠진 나머지가 나누는 숫자보다 작아지면 계산을 그만하기위한 반복문
    if n%i == 0: 
        prime.append(i)
        n = n//i
    else:
        i += 1

list(set(prime))
print(prime[-1])

 

600851475143란 숫자 대신 생각하기 쉬운 140이란 숫자를 가지고 알고리즘을 구상했다. 

n을 2부터 시작해 나눠질때까지 나누고 더이상 나눠지지 않으면 1식 늘려가면서 나머지를 나눈다. 나누는 수를 prime이란 리스트에 넣어서 계산을 마친 후에 가장 큰수를 print한다. 

 

처음 코드를 짤때 while 반목문을 넣지않았고 for i in range(2, n)이라고 적었다. 그러면 더 이상 나눠지지 않는 데도 계산 연산을 하고 있어서 처리속도가 눈에 띄게 느렸다.  이를 해결하기 위해 i가 나눠지는 수인 n을 넘어가면 반복문을 끝내게 코드를 작성하였다. 

답: 6857