[수학] [BJ2609] 최대공약수와 최소공배수

코드 플러스

🚩 문제 설명

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

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

BJ2609

 

⏱️ 시간 복잡도
▪ 최대공약수, 최소공배수 모두 O(N)의 시간복잡도로 구할 수 있다.

◾ 두 수의 최대공약수와 최소공배수를 구하는 문제

◾ 최대공약수 (Greatest Common Divisor)

• 두 수의 공통된 약수 중에서 가장 큰 정수
• 최대공약수가 1인 두 수는 서로소 (Coprime) 라고 한다.
• 구하는 방법
  1. 2부터 min(A, B)까지 모든 정수로 나누어 본다.
  2. 유클리드 호제법을 사용한다.
     • gcd(a, b) == gcd(b, a%b)
     • r == 0 이면 그때 b가 최대공약수 이다.

# 2부터 min(a, b) 까지 나눠서 구하는 방법

gcd_ = 0
for i in range(2, min(a, b)):
	if a % i == 0 and b % i == 0:
    	gcd_ = i

# 유클리드 호제법

def gcd(a, b):
	if b == 0:
    	return b
    else:
    	return (b, a%b)

# 재귀 사용하지 않은 유클리드 호제법

r = 0
def gcd(a, b):
	while b != 0:
    	r = a % b
        a = b
        b = r
    return a

◾ 최소공배수 (Least Common Multiple)

• 두 수의 공통된 배수 중에서 가장 작은 정수
• lcm = gcd * (a / gcd) * (b / gcd)

 

 

 

---

 

 

 

✅ 입출력

1) 두 개의 자연수가 주어진다.
return ➡️ 두 개의 자연수의 최대공약수와 최소공배수를 구한다.

✔️ 예제 1

24 18

6
72

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from math import gcd


def lcm(a, b, gcd):  # 최소공배수
    lcm_ = (a // gcd) * (b // gcd) * gcd
    return lcm_


a, b = map(int, sys.stdin.readline().split())
gcd_ = gcd(a, b)

print(gcd_)
print(lcm(a, b, gcd_))

💬 Point

➡️  from math import gcd 사용
➡️  gcd를 이용하여 lcm 구하기

◾ math 라이브러리를 활용하여 gcd를 구하였다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 수학 최대공약수와 최소공배수

# 백준 2609 최대공약수와 최소공배수 파이썬 python

---