Problem_003_Largest prime factor

[그림 01] Problem 003 문제

문제를 살펴보면 다음과 같습니다.

문제 이름 : 가장 큰 소수는?

문제 내용 : 13195의 소수들은 5, 7, 13 그리고 29로 이루어져 있습니다. 즉, 5*7*13*29가 13195라는 것입니다. 그렇다면 600851475143에서 가장 큰 소수는 무엇입니까?

우리는 다음과 같은 조건을 가진다는 것을 알 수 있습니다.

1. 600851475143이라는 숫자는 소수의 곱으로만 이루어져 있음

2. 소수를 구하여 위의 숫자를 나누어주고, 그 중 가장 큰 녀석을 찾아내야 함

이제 소스코드를 작성해보도록 합시다.

#Project Euler Problem 003
#Python 3 version source

#13195 는 5 x 7 x 13 x 29라는 소수로 이루어져 있다. 600851475143에서 가장 큰 소수는 무엇인가?

#getPrime == 소수 구하기 함수
def GetPrimeAndDivision(Value):
	primeList = [2]           #소수 리스트 생성
	divideList = list()       #나누어지는 소수의 리스트
	num = 3                   #3부터 소수인지 검사함
	
	while(num <= Value):
		for x in primeList:
			if(num % x == 0):         #소수로 나누었을 대 나누어지면 소수 아님
				break
			elif(x == primeList[-1]): #소수리스트의 끝원소로도 나누어지지 않으면 소수
				primeList.append(num)	            #구한 소수를 소수 리스트에 추가
				if Divide_LimitValue(num, Value): #참 값이 반환되면 실행
					divideList.append(num)
					Value = Value / num
				break
		num += 1
	
	return divideList
	
def Divide_LimitValue(PrimeNum, LimitValue): #소수로 값을 나눠보도록 함
	Answer = LimitValue % PrimeNum
	if Answer == 0: #소수가 나누어 떨어지면 나누어지는 소수 값을 반환
		return PrimeNum
	else:
		return 0
		
if __name__ == "__main__":
	Main_LimitValue = 600851475143
	Main_FactorList = list()
	i = 0
	
	Main_PrimeList, Main_DivideList = GetPrimeAndDivision(Main_LimitValue)
	print("Main Divided List : ", Main_DivideList)

메인에서는 소수로 곱해진 값을 정의해주었고, 함수를 하나 실행할 뿐입니다.

그리고 GetPrimeAndDivision에서는 한계값을 받아오고, 그 값보다 작은 소수를 찾아내어 Divide_LimitValue를 통해서 나누어떨어지는지 확인합니다.

확인이 완료되면, 그 값을 divideList에 append해주고, 600851475143을 나누어지는 소수로 나누어 다음 값을 알아내도록 합니다.

완료가 되면, Main_DivideList로 받아 출력하도록 하였습니다.

저보다 굉장한 사람은 늘 있습니다.

참고하고자 소스를 가져왔습니다.. 흑흑 비교가 많이 되지만 이를 참고하여 점점 더 발전해야지요.

출처 : http://www.s-anand.net/euler.html

n = 600851475143
i = 2

while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1
    
print(n)

막상 보니까 겁나 짧네요. 헛웃음이 슬쩍 저를 찌르고 들어갑니다.

저는 비로소 이 소스를 보고 이렇게 될 뿐이었습니다.

생각해보니 그렇습니다.

어차피 n에 저장되어 있는 값은 소수들의 곱으로 이루어져 있습니다. 즉, 나누어 떨어진다면, 그 숫자는 소수라는 것입니다.

그렇다면, 그냥 나누어 떨어지기만 하는 것을 쭉 골라내고, 만약 더 이상 나누어지지 않으면 출력하면 됩니다.

헉헉... 쩐당... 기존의 조건을 활용하다니. 닫인 머리뚜껑을 열어야 합니다 흑흑!!!