[백준 파이썬 2609번]최대공약수와 최소공배수★gcd,lcm★유클리드함수★

1. math library 의 gcd , lcd 모듈 사용하기

import math

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

print(math.gcd(a, b))
print(math.lcm(a, b))

2. 유클리드 함수 사용하기

import sys

A= list(map(int,sys.stdin.readline().rstrip().split()))
A= sorted(A , reverse=True)
seo, dae = 0,0
if A[0]%A[1] ==0:
    seo = A[1]
    dae = A[0]
else:
    a,b = A[0],A[1]
    while True:
        temp = a%b
        if temp !=0:
            a = b
            b= temp
        elif temp == 0:
            seo = b
            break
    dae = A[0]*A[1]//seo
print(seo)
print(dae)

==> seo --> 최소공배수

        dae --> 최대공약수

 

else 문 ==>

ex) 22와 4

1) temp =   22 % 4 = 2

 

a = 4

b = 2 

 

2) temp = 4%2 = 0

seo = 2

dae = 22*4//2 = 44 

 

유클리드 함수는 두개를 나누고 나눈 몫에 대하여 나머지가 0이 나올때까지의 수 ==> 최소공배수를 구할 수 있다.