최소공배수 문제

중간고사 공부하다가 푼 문제 ~~

 

 

a < b를 만족하는 a와 b를 입력받고,

a부터 b까지 범위의 모든 정수의 배수이면서 가장 작은 값을 갖는 수를 찾는 문제이다.

 

---

맨 앞 두 수의 최소공배수를 구하고,

그 수와 다음 수의 최소공배수를 구하는 식으로 코드를 작성해 보았다..

 

이게 맞나?

아무튼 해보았다.

---

최소공배수를 구할 때에는

(두 양의 정수의 최소공배수) = (두 수의 곱) / (두 수의 최대공약수) 를 이용하였다.

 

먼저 재귀함수로 유클리드 호제법을 구현하여 최대공약수를 구해준 뒤, 이를 이용하여 최소공배수를 구해주었다.

 

def GCD(a,b):
  if a % b == 0:
    return b
  else:
    return GCD(b,a%b)

def LCM(a,b):
  return a * b // GCD(a,b)
  
a = int(input('범위의 시작 정수 : '))
b = int(input('범위의 마지막 정수 : '))

temp = LCM(a,a+1)

for i in range(a+1,b):
  temp = LCM(temp,i+1)

print('{}에서 {}까지 정수들의 최소 공배수는 : {}'.format(a,b,temp))

 

출처: 으뜸 파이썬 연습문제 4-18