[Python] 파이썬- 최대공약수, 최소공배수

최대공약수/ 최소공배수

• 최대공약수 GCD(Greatest Common Divisor) : 두 수의 공통 약수 중 가장 큰 수
• 최소공배수 LCM(Largest Common Multiple) : 각각의 배수 중 공통이고, 가장 작은 수

 

for문 활용한 최대공약수/최소공배수

• 최대공약수
  • a,b중 가장 작은 값 부터 1까지 -1을 하며 for문 실행 : 큰 값부터 실행
  • a와 b가 처음으로 동시에 나눠떨어지는 값이 최대공약수

#최대공약수
def GCD(a,b):#최소공배수
  for i in range(min(a,b),0,-1):
    if a%i==0 and b%i==0:
      return i
      break

print(GCD(10,12))
#결과
2

• 최소공배수
  • a,b중 더 큰 숫자부터 a*b까지 증가시키며 for문 실행
  • i 값을 a와 b로 나눴을 때 처음으로 모두 나눠떨어지는 값: 최소공배수

#최소공배수
def LCM(a,b):
  for i in range(max(a,b), a*b+1):
    if i%a==0 and i%b==0:
      return i
      break

print(LCM(3,5))
#결과
15

 

유클리드 호제법

• 최대공약수
  • x와 y의 최대공약수는 y와 r의 최대공약수와 같다 ( r = x%y (x를 y로 나눈 나머지 값) )
  • x←y , y←r 을 대입하여 위의 방식 반복
  • x%y==0 이 되는 때의 y 값: 원래 x,y의 최대 공약수 
  • x%y==0 이 되는 때의 y 값 = 이전 while문에서 x에 넣은 값
• 최소공배수
  • (x*y) // GCD(x,y) : x*y 를 최대공약수로 나눈 몫

#최대공약수
def GCD(x,y):
  while(y): #y가 참일 동안 = y가 자연수일 때 = x%y!=0
    x,y=y,x%y
  return x

print(GCD(10,12))

#최소공배수
def LCM(x,y):
  result= (x*y)//GCD(x,y)
  return result

print(LCM(10,12))

#결과
2
60

 

 

참고) https://codingpractices.tistory.com/34