https://www.acmicpc.net/problem/2609
1. 문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
2. 풀이
2-1. 접근
최대공약수와 최소공배수를 구하기 위해선, 우리 모두가 아는 방법 "소인수 분해"가 있음
이를 어떻게 컴퓨터에 명령할 것이냐?가 관건일듯
2-2. 소인수분해 프로그래밍
https://thebook.io/007026/0257/
# 소인수분해 프로그램
x = int(input("?")) # 소인수분해할 숫자를 입력받아 정수로 바꿉니다.
d = 2 # 가장 작은 소수인 2부터 나눕니다.
while d <= x:
if x % d == 0: # x가 d로 나누어지면(나머지가 0이면)
print(d) # d는 x의 약수이므로 출력합니다.
x = x / d # x를 d로 나눠서 다시 x에 저장합니다.
else:
d = d + 1 # 나누어지지 않으면 1을 더해서 반복합니다.--> 하지만,,, 최소공배수 같은 경우는 모든 수를 곱하면 되니까 어떻게 한다고 쳐도, 최대공약수 같은 경우엔 특정 숫자만 뽑아내서 계산해야하는데, 이를 알아내는 알고리즘을 도무지 생각해봐도 모르겠다..
이번 문제 못 풀겠읍니다.. 포기,,
그래서 구글링으로 답안 찾기
2-3. Math lib
지난번에도 나왔고, 이번에도 나온다.
Math 라이브러리 내 최대공약수와 최소공배수가 계산 가능한 함수가 있었음
gcd(최대공약수)와 lcm(최소공배수) 함수 사용하기
import math
a, b = map(int, input().split())
print(math.gcd(a, b))
print(math.lcm(a, b))2-4. 유클리드 호제법
def Euclidean(a, b):
r = b % a
if r == 0:
return a
return Euclidean(r, a)
- a & b의 최대 공약수는 b & a를 b로 나눈 나머지의 최대 공약수와 같음 -> a,b = b, a%b
- 최소공배수는 a와 b의 곱을 a와 b의 최대 공약수로 나눈 값
n, m = map(int, input().split())
def gcd(n, m):
while(m):
n, m = m, n % m
return n
print(gcd(n,m))
def lcm(n, m):
result = (n * m) // gcd(n, m)
return result
print(lcm(n, m))
Newbie