컴퓨터를 다루다

[그림 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에 저장되어 있는 값은 소수들의 곱으로 이루어져 있습니다. 즉, 나누어 떨어진다면, 그 숫자는 소수라는 것입니다.

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

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

[그림 01] Problem 002 문제

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

문제 이름 : 짝수 피보나치 숫자들

문제 내용 : 각 단계마다 피보나치가 생성되는데, 피보나치의 다음 단계는 두 개의 단계(번째)를 더하여 생성됩니다. 1과 2로 시작하여 10단계를 생성해보면 다음과 같이 생성됩니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ....

이제 이를 고려하여 4,000,000(4백만, 4million)을 넘지 않는 각 단계를 계속 생성할 때, 생성된 값이 짝수들인 단계를 모두 더한 값을 구하십시오.

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

1. 피보나치의 원리를 이용하여 다음 단계를 계속 생성함

2. 생성된 단계가 400만을 넘지 않아야 함

3. 생성된 값 중 짝수인 것을 모두 더해야 함

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

#Project Euler Problem 002
#Python 3 version source
#even-valued terms' Sum value --> 짝수의 값으로 나오는 term을 모두 더함

def Define_Fibonacci(ex_number, number):	#피보나치 생성함수
	next_number = ex_number + number
	return number, next_number

def Even_Value_Sum(Fibo_list):		        #짝수 값을 구분하여 더함
	Even_Fibo_Sum = 0
	for i in range(len(Fibo_list)):
		if Fibo_list[i] % 2 == 0:
			Even_Fibo_Sum += Fibo_list[i]
	return Even_Fibo_Sum

if __name__ == "__main__":
	Fibonacci_Limit = 4000000       #피보나치 값이 넘지 않아야 할 한계값
	Fibonacci_Sum = 0               #피보나치 짝수 값을 더할 변수
	Fibonacci_List= [1,2]           #피보나치 배열
	i = 0
	
	while True:
		main_num, main_next_num = Define_Fibonacci(Fibonacci_List[i],Fibonacci_List[i+1])
		if main_next_num <= Fibonacci_Limit: #피보나치 값이 한계값을 넘지 않으면 피보나치 배열에 추가함
			Fibonacci_List.append(main_next_num)
		else:	                               #400만을 넘는 값이 생성되면 출력하고 종료
			print("Even Fibo Sum : ", Even_Value_Sum(Fibonacci_List))
			break
		i += 1                 #While문의 횟수를 표시
	#print(Fibonacci_List)   #피보나치 배열을 출력할 수 있음

위의 소스는 문제를 해결하는 소스입니다.

먼저 메인에서는 한계값을 지정한 변수, 더해줄 변수, 피보나치 배열을 선언합니다.

그리고 While 무한 반복으로 피보나치 단계 중 400만이 넘는 값이 나오기 전까지 반복해줍니다.

Define_Fibonacci를 통해 다음 피보나치 단계를 생성하고, Even_Value_Sum을 통해 피보나치 리스트에 있는 값 중 짝수 값을 골라 더해주고, 이를 반환해줍니다.

그리고 이외에 홀수, 그리고 피보나치 배열의 모든 값을 더하는 기능을 추가한 소스는 다음과 같습니다.

#Project Euler Problem 002
#Python 3 version source
#even-valued terms' Sum value --> 짝수의 값으로 나오는 term을 모두 더함

def Define_Fibonacci(ex_number, number):
	next_number = ex_number + number
	return number, next_number

def Even_Value_Sum(Fibo_list):
	Even_Fibo_Sum = 0
	for i in range(len(Fibo_list)):
		if Fibo_list[i] % 2 == 0:
			Even_Fibo_Sum += Fibo_list[i]
	return Even_Fibo_Sum

def Odd_Value_Sum(Fibo_list):
	Odd_Fibo_Sum = 0
	for i in range(len(Fibo_list)):
		if Fibo_list[i] % 2 == 1:
			Odd_Fibo_Sum += Fibo_list[i]
	return Odd_Fibo_Sum
	
def Whole_Value_Sum(Fibo_list):
	Whole_Fibo_Sum = 0
	for i in Fibo_list:
		Whole_Fibo_Sum += i
	return Whole_Fibo_Sum
	
if __name__ == "__main__":
	Fibonacci_Limit = 4000000
	Fibonacci_Sum = 0
	Fibonacci_List= [1,2]
	i = 0
	
	while True:
		main_num, main_next_num = Define_Fibonacci(Fibonacci_List[i],Fibonacci_List[i+1])
		if main_next_num <= Fibonacci_Limit:
			Fibonacci_List.append(main_next_num)
		else:
			print("Even Fibo Sum : ", Even_Value_Sum(Fibonacci_List))
			print("Odd Fibo Sum  : ", Odd_Value_Sum(Fibonacci_List))
			print("Whole Fibo Sum: ", Whole_Value_Sum(Fibonacci_List))
			break
		i += 1
	#print(Fibonacci_List)	

늘 느끼는 거지만, 저보다 잘하는 사람은 늘 있습니다.
출처 : http://www.s-anand.net/euler.html

cache = {}     #dict == dictionary 형태의 타입 // type(cache) == 'dict'
def fib(n):
	cache[n] = cache.get(n, 0) or (n <= 1 and 1 or fib(n-1) + fib(n-2))
	return cache[n]

n = 0
i = 0

while fib(i) <= 4000000:
    if not fib(i) % 2: n = n + fib(i)
    i = i + 1

print(n)

[그림 01] Problem 001의 문제

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

문제 이름 : 3과 5의 배수

문제 내용 : 만약 10 미만의 숫자 중에서 3이나 5의 배수인 것을 골라보았을 때, 우리는 3, 5, 6 그리고 9를 얻을 수 있습니다. 그리고 그들의 합은 23입니다. 3과 5의 배수 중 1000 미만의 숫자를 골라서 그들의 합을 구하십시오.

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

1. 3과 5의 배수를 모두 골라내야 함

2. 골라낸 배수들을 모두 더해야 함

3. 골라낸 배수들은 절대 1000이상이 되어서는 안 됨

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

#project euler Problem 001
#python 3 version source
def find_multiples(number): #3과 5의 배수를 구하는 함수
	temp01 = number % 3
	temp02 = number % 5
	
	if temp01 == 0 or temp02 == 0:
		return number
	else:
		return 0

if __name__ == "__main__":
	limit = 1000 #한계 범위
	answer = 0
	
	for i in range(3,limit): #3에서부터 한계범위
		answer += find_multiples(i)
		
	print(answer)

find_multiples 함수는 숫자를 인자값으로 받아서 이 값이 3의 배수이거나 5의 배수인지를 검사한 후 만약 참일 때 리턴하여 더할 수 있도록 하였고, 만약 거짓일 경우 0을 더하는(더하나 마나 하는 행위) 기능을 합니다.

그리고 모두 더해진 값을 print()로 출력하게 됩니다.

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

저는 그 분들의 소스를 참고하고자 합니다.

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

n = 0
for i in range(1,1000):
	if not i % 5 or not i % 3:
		n = n + i
print(n)

맞아..! not이 있었어어어...!!!

P.S python 3.0에서는 xrange가 사라졌습니당. 기존의 range()의 범위가 들쭉날쭉하던 것을 python 3.x에서는 xrange == range로 바꾸었습니다.