[프로젝트 오일러] 3번 문제 & 풀이 (가장 큰 소인수 구하기)

Problem 3

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

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

 

내 아이디어

1. 2부터 차례로 나누기 시작
2. 나누어진 숫자가 나오면, 그 숫자로 한번 더 나눌 수 있도록 조건문의 처음으로 돌아가도록 설정 -> while & if 함수 사용
3. 이와 같은 방식으로 나누는 숫자를 1씩 증가시키며 나눈다.
4. 나누는 숫자가 나누는 숫자보다 더이상 작지 않으면 조건문 종료 (즉, 자기 자신을 나눌 때 종료)
5. 마지막 나누는 숫자가 정답

num = 600851475143
a = 2

while a < num:
    if num % a == 0:
        num /= a
    else:
        a += 1

print(num)

결과 :

6857.0

 

다른 아이디어

1. 2부터 나누기 시작하여 나누어 떨어지면 리스트에 추가한다.
2. 나누어진 숫자가 나오면, 그 숫자로 한번 더 나눌 수 있도록 조건문의 처음으로 돌아가도록 설정 -> while & if 함수 사용
3. 이와 같은 방식으로 나누는 숫자를 1씩 증가시키며 나눈다.
4. 마지막으로 나누어 몫이 1이 나오면 조건문 종료
5. 리스트 목록 중 제일 큰 값이 정답

num_list = []
num = 600851475143
i = 2

while num > 1:
    if num % i == 0:
        num /= i
        num_list.append(i)
    elif num == 1:
        break
    else:
        i += 1

print(num_list)
print(max(num_list))

결과 :

[71, 839, 1471, 6857]

6857