Project Euler - 003

Project Euler - 003(Largest prime factor)

사이트

영어 : https://projecteuler.net/problem=3
한글 : http://euler.synap.co.kr/prob_detail.php?id=3

문제

영문

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 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.

풀이과정

1. 소인수가 저장될 리스트lst = []를 만든다.
2. 소인수는 2부터 시작한다.
3. 구하고자 하는 수를 2로 나누어 떨어진다면 2는 소인수이다. 그렇다면 다음 수를 구하기위해 원 수에서 x를 나누어 나온 몫을 다시 구하고자 하는 수에 넣는다.
4. 만약 나누어 떨어지지 않는다면 그 수는 소인수가 아니고 하나를 증가(x+1)시켜 다시 계산하도록 한다.
5. 제수가 피제수보다 커지면 모든 소인수를 다 구한 것이다.(더이상 나눌 수가 없음)

내가 푼 답안

lst = []         # 소인수가 저장될 리스트 

n = 600851475143 # 소인수 구할 수 

x = 2            # 최초로 나눌 수(나눠지지 않으면 +1 씩 커진다) 



'''

n(피제수 : 나누어 지는 수)이 x(제수 : 나누는 수)로 나뉘게 될 때

제수(x)가 피제수(나누어 지는 수) 보다 커지면 반복문을 종료한다.

'''

while x <= n:

    if n % x == 0:    # 피제수가 제수에 나누어 진다면 x는 n의 소인수 이다. 

        lst.append(x) # 소인수를 리스트에 추가 

        n /= x        # 피제수를 소인수로 나눈 몫을 다음 피제수로 한다. 

    else :

        x += 1        # 나누어 지지 않는다면 소인수가 아님(제수를 하나 증가시킨다) 



print(lst)

#Project_Euler #question3 #프로젝트_오일러 #python3