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

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

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

---

나의 코드

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))