[프로젝트 오일러] Python 3번 문제

[문제]

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

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

 

[알고리즘]

1. 소인수 정의 : 1과 자기 자신으로만 나누어지는 수

2. 2부터 시작해서 n을 나누어 준다.

3. 2로 나누어지면 다시 2로 나누어주고 나누어지지 않으면 1을 더한 수로 반복

4. 마지막으로 나누어진 수가 소인수 중 가장 큰 값.

 

* 3번 과정을 이해하는 게 중요하다. 처음에 num = num/factor를 해주는 이유를 생각하지 못했음.

종이에 수를 써놓고 인수분해 하는 과정을 생각하면 쉽게 이해할 수 있다.

[코드]

def prime_factor(num):

    factor=2

    while not num == 1:

        if num%factor == 0:

            print(num,factor)

            num = num/factor

        else:

            factor+=1

    return factor

n = 600851475143

print(prime_factor(n))