본문 바로가기
공부/알고리즘

[알고리즘][백준] 2609번 최대공약수와 최소공배수 - 파이썬(python) 풀이

by 무명오리 2024. 2. 27.

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

 

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

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net


나의 코드

import sys

n, m = map(int, sys.stdin.readline().split())
num = n if n > m else m
m_yak = []

for i in range(1,num):
    if (n % i == 0) and (m % i == 0):
        m_yak.append(i)

print(max(m_yak))
       
a = 1
while a:
    if (n*a) % m == 0:
        print(n*a)
        break
    a += 1

틀렸다고 떠서 무엇인가 보니....

 

 

n과 m 둘중에 최소공약수가 나올수있기 때문에 range(1, num+1)로 수정!

import sys

n, m = map(int, sys.stdin.readline().split())
num = m if n > m else n     # min(n, m)
m_yak = []

for i in range(1,num+1):
    if (n % i == 0) and (m % i == 0):
        m_yak.append(i)

print(max(m_yak))
       
a = 1
while a:
    if (n*a) % m == 0:
        print(n*a)
        break
    a += 1

 

 

 

다른 분들의 코드를 보니 유클리드 호제법이라고 따로 공식이 있다한다...

a를 b로 나누고 나눈수를 다시 나머지로 나누다 나머지가 0이 나올때까지 반복하는 식

a % b = c

b % c = d

c % d = 0 --> d가 최대공약수

while b != 0 :
    a = a % b
    a, b = b, a
print(a)
 
def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m%n)

print(gcd(m, n))
print(m*n//gcd(m, n))

 

그런데 이미 math 모듈에 최대공약수, 최소공배수 구하는 함수가 내장되어 있다고....

import math
import sys

n, m = map(int, sys.stdin.readline().split())
print(math.gcd(n, m))
print(math.lcm(n, m))