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

📌생각해보기

1. 최대공약수를 어떤 방법으로 계산할 수 있을까?
   -> 유클리드 호제법을 사용하면 간단하게 계산할 수 있다.
   
   💡유클리드 호제법:
   2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
   c = a % b
   a = b
   b = c

2. 최소공배수를 어떤 방법으로 계산할 수 있을까?
   -> 피연산자들을 곱해서 최대공약수를 나누면 구할 수 있다.

📌내가 작성한 코드

import sys

A, B = map(int, sys.stdin.readline().split())
a, b = A, B

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

print(a)
print(A*B//a)

📌풀이

💡 다른 방법으로는 함수로 만들어도 수월하게 된다.

def gcd(a, b):
    while a % b > 0:
        c = a % b
        a = b
        b = c
    return b

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

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

💡 더 쉽게는 파이썬에서는 최대공약수, 최소공배수를 구할 수 있는 내장함수가 있다.

<import math

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