Baekjoon 문제 풀기 (2609번 : 최대공약수와 최소공배수) Python

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

1. 문제읽기

---

유클리드 호제법을 이용한 문제

수학 공식을 이용한 문제는 좀 안나왔으면 좋겠다.

2. 제출 코드

---

요즘 소수문제만 풀었더니 소수로 문제를 해결할려고 난리를 쳤다.
이렇게 푸는게 아닌 줄 알면서도 오기가 생겨서 예제 1번은 어떻게어떻게 정답을 출력했다.
그러나 처참하게 실패!!

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

def func(num):
	ans = []
	prime_arr = primeArray(num)
	while 1:
		for i in prime_arr:
			if num%i ==0:
				if num//i == 1:
					ans.append(num)
					return ans
				ans.append(i)
				num = num//i
				if num in prime_arr:
					ans.append(num)
					return ans

def isPrime(num):
	if num == 1:
		return False
	sq = int(num ** 0.5)
	for i in range(2, sq+1):
		if num%i == 0:
			return False
	return True

def primeArray(num):
	prime_arr = []
	for i in range(2, num+1):
		if isPrime(i):
			prime_arr.append(i)
	return prime_arr

ans_arr = list(set(func(a)-func(b)))
ans = 1
print(ans_arr)
for i in ans_arr:
	ans *= i
print(ans)
a_ans = a//ans
b_ans = b//ans
ans_ans = a_ans*b_ans*ans
if ans_ans == 0:
	print(1)
else:
	print(ans_ans)

3. 공부할 것

---

유클리드 호제법

최대공약수를 구하는 방법.
a를 b로 나눈 나머지를 r이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수이다.
단, a>b이다.

위 방법으로 b를 나머지를 0이 될때까지 계속 나눠서 최대공약수를 구할 수 있다.

최소공배수 구하기

최대공약수 : gcd = greatest common divisior
최소공배수 : lcm = least common multiple

a = gcd * x
b = gcd * y
(단, x, y는 서로소이다.)
a * b = gcd * gcd * x * y
lcm = gcd * x * y 이므로 lcm = a * b / gcd 가 도출된다.

math모듈 gcd, lcm 메소드

math 내장 모듈에 최대공약수와 최소공배수를 구하는 함수가 있다.

import math

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

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

정답 코드

a가 반드시 b보다 크다는 이야기가 없어서 x, y를 따로 지정해주었다.

a가 24이고 b가 18일 때, 유클리드 호제법을 적용하면 24와 18의 gcd는 18과 24%18의 gcd와 같다.
이걸 반복하면 아래와 같이 나타낼 수 있는데, 나머지가 0일 때 x값이 gcd가 된다.
gcd(24,18) -> gcd(18,24%18=6) = gcd(18,6) -> gcd(6, 18%6=0)

최소공배수 구하는 공식이 위에 언급한 것처럼 a*b%gcd라는데, 이해가 잘 안되서 그냥 알고있는 서로소 * gcd로 해결했다.
a와 b를 각각 gcd로 나누면 서로소가 된다.

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

x = max(a, b)
y = min(a, b)

while y>0:
    x, y = y, x%y

print(x)
print(x*(a//x)*(b//x))