[백준] 2609번 최대공약수와 최소공배수 - 파이썬(Python)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

문제

 

21.02.14 접근법

 

• 최대공약수(GCD) - 두 수를 공통으로 나눌 수 있는 수 중 제일 작은 수
  • [유클리드 알고리즘]
  • a/b를 후 나머지를 a에 저장
  • a와 b의 값을 서로 바꾸고, 다시 a와 b를 나눔 - 나머지 나누기 b를 하기 위함
  • 나머지가 0될 때까지 반복 - 나머지가 0이 되면 마지막으로 나누게 된 나머지가 최대공약수

 

• 최소공배수 - 두 수의 공통인 수들 중, 제일 작은 공배수
  • a와 b를 곱하고 최대공배수로 나눈 값이 최소 공배수

 

 

21.02.14 코드

a,b=map(int,input().split())
aa,bb=a,b

while bb!=0:
    aa=aa%bb
    aa,bb=bb,aa

lc=a*b//aa

print(aa)
print(lc)

 

21.08.09 접근법

 

최대공약수(GCD) - 유클리드 알고리즘 사용

최소공배수 - 입력받은 값에서 GCD를 나눠 나온 몫들과 GCD를 곱함.

 

 

21.08.09 코드

import sys

a,b=map(int,sys.stdin.readline().split())
aa,bb=a,b

while a%b!=0:
    a,b=b,a%b

print(b,aa//b*bb//b*b,sep=('\n'))