Problem_005_Smallest Multiple

[그림 01] Problem 005 문제

문제 제목 : 가장 작은 최소공배수

문제 내용 : 2520은 1이상 10이하로 모두 나누어지는 숫자 중 가장 작은 값(최소공배수)입니다. 그렇다면, 1이상 20이하의 최소공배수(모두 나누어지는 가장 작은 수)

※ evenly divisible : 고르게, 골고루 나누어 질 수 있는

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

1. 최소공배수가 되는 녀석을 알아내야 함

2. 소수는 다 들어 있을 것임

위의 조건으로 먼저 손으로 풀어보니(노가다가 좀 있었습니다), 5 * 7 * 9 * 11 * 13 * 16 * 17 * 19이 정답이 되었습니다.

그런데 이걸 어떻게 규칙으로 만들어야 하나.... 손으로 많은 고민을 해본 결과 다음과 같은 규칙을 알게 되었습니다.

일단 소수를 모두 구한 후, 소수가 아닌 녀석들을 한 번 보았습니다.

소수 : 2, 3, 5, 7, 11, 13 ,17, 19

소수가 아닌 값 : 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20

그리고 정답의 9와 16을 보니, 20보다 작은 소수의 제곱이었습니다.

9는 3^2, 16은 2^4입니다.

그리고 나머지 소수는 제곱만 해도 20을 넘기 때문에 제외되는 것이었습니다.

이제 위의 내용을 통해 소스 코드를 작성해보도록 합시다.

#Problem 005
#Python 3 version source

#answer = 5*7*9*11*13*16*17*19

def getPrime(primeRange):
	primeList = [2] #소수 리스트
	number = 3      #소수 시작 숫자
	
	while(number <= primeRange):
		for i in primeList:
			if(number % i == 0):      #기존의 소수로 나누어지면 소수가 아님
				break
			elif(i == primeList[-1]): #마지막 소수로도 안 나눠지면 소수 
				primeList.append(number)
				break
		number += 1
	
	return primeList
	
if __name__ == "__main__":
	Main_Smallest_Num_Range = 20
	Main_primeList = getPrime(Main_Smallest_Num_Range)
	Main_elseList = list()
	Main_Answer = 1
	Main_Exception = set([2,3])
	
	#Main_Smallest_Num_Range를 넘지 않을 때까지 제곱을 함
	for i in Main_primeList:
		num = i
		while True:
			if num * i > Main_Smallest_Num_Range:
				break
			num *= i
			
		Main_elseList.append(num)
	
	#Main_Set은 최소공배수에 들어갈 최종 리스트들임
	#Main_primeList : 소수들의 리스트
	#Main_elseList  : 소수가 아닌 것들의 제곱 리스트
	#Main_Exception : 2와 3은 제외되기 때문에 제외시킬 리스트
	#Main_Answer    : 최소공배수 값(답)
	Main_Set = set(Main_elseList + Main_primeList) - Main_Exception
	
	#최소공배수를 만드는 함수
	for i in Main_Set:
		Main_Answer *= i
	
	print("Set List : ", Main_Set)
	print("Answer   : ", Main_Answer)

소스 못 쓸 줄 알았는데 다행이 써지네요.

신난다요.

이제 저보다 잘하는 사람의 답을 가져와보도록 합시다.

def gcd(a,b): return b and gcd(b, a % b) or a
def lcm(a,b): return a * b / gcd(a,b)

n = 1

for i in range(1, 21):
    n = lcm(n, i)
print(n)

아....!

[그림 02] 마...맞다....! gcd... lcm은 또 뭐지..!?

겁나 잘하네요... 저는 gcd, lcm의 존재를 모르고 있었습니다...

이번에는 나름 멋지게 짠 거라고 생각했거늘, 버젓이 gcd, lcm이라는 기능이 있었네요 헿.

gcd는 최대공약수 함수이며, lcm은 최소공배수 함수입니다.

gcd(a, b) : a와 b의 최대공약수를 구하여 return함

lcm(a, b) : a와 b의 최소공배수를 구하여 return함

gcd와 lcm을 만들어서 활용할 수 있는 방향도 있군요..!

P.S. python에서는 gcd와 lcm을 지원하지 않습니다. 때문에 두 번째 소스에서는 gcd와 lcm을 맞춤형으로 선언한 것을 알 수 있습니다.