[프로젝트 오일러/파이썬] Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

(어떤 수를 소수의 곱으로만 나타내는 것을 '소인수분해'라고 하며, 이 소수들을 그 수의 '소인수'라고 합니다.)

13195의 소인수는 5, 7, 13, 29 이다.  # 5 * 7 * 13 * 29 = 13195
숫자 600851475143의 가장 큰 소인수는 무엇입니까?

 

# 사전 지식

- 소수 : 1과 그 자신만을 약수로 가지는 수 ( 소수는 약수가 2개이다.)

- 1 은 소수가 아니다.

- 소수 중 유일한 짝수는 2 이다.

- '2'를 제외한 나머지 소수들은 전부 3 이상이며 홀수이다.

- 소인수 분해를 계속해서 진행하면, 결국 마지막 소수로 나눌 때는 나머지가 0 이 된다.

  숫자가 마지막 소수의 거듭제곱으로 이루어져 있어도 결국 나머지는 0 이 된다.

- 나누어 떨어지면 현재의 소수를 유지하고, 나누어 떨어지지 않으면 +2 를 한다. (유일한 짝수 소수 2)

 

 

# 풀이

1 을 넣으면 False 를 반환.

2 부터 시작해서 나누어지는 수가 1 이 될 때까지 계속 나누어 가는 방식.

코드 상으로는 나누는 수(factor)를 1 씩 증가시키면서 원래의 수를 나누어 떨어질 때마다 나누어서 크기를 줄여 나간다. 원래의 수가 최종적으로 1이 되면, 그때의 나눈 수(factor)가 가장 큰 소인수(prime_factor)가 된다.

이 방법은 프로그래밍이라기 보다는 수학적인 해결 방법에 가깝다.

 

a = int(input('숫자를 입력하세요: '))  # 600851475143
 
def prime_factor(num):
    if num == 1:
        return False
    else:
        factor = 2
        while num != 1:
            if num % factor == 0:
                num = num / factor
            else:
                factor += 1
        return factor
 
print(prime_factor(a))  # 답: 6857