[알고리즘] gcd, lcm

최대공약수, 최소공약수를 구하는 알고리즘입니다.

최대공약수

# 변수 선언 및 입력
n, m = map(int, input().split())


# n과 m의 최대공약수 반환
def find_gcd(n, m):
    gcd = 0
    for i in range(1, min(n, m) + 1):
        if n % i == 0 and m % i == 0:
            gcd = i

    print(gcd)


find_gcd(n, m)

최소공배수

최소공배수는 두 수 a,b가 주어졌을 때 ab/(a와 b의 최대공약수)로 구할 수 있다.
최대 공약수는 1부터 min(a,b)까지 수 중에서 a,b 모두로부터 나누어떨어지는 최댓값인데, gcd(a,b) 라고 하면
최소공배수는 ab/gcd(a,b)라 할 수 있다.

# 변수 선언 및 입력
n, m = map(int, input().split())


# n과 m의 최소공배수 출력
def find_lcm(n, m):
    gcd = 0
    for i in range(1, min(n, m) + 1):
        if n % i == 0 and m % i == 0:
            gcd = i

    print(n * m // gcd)
   

find_lcm(n, m)