[프로그래머스] 최대공약수와 최소공배수 - math, gcd, lcm

 

# 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12940?language=python3

프로그래머스

 

 

# 문제 요약

 

최대공약수 (gcd), 최소공배수 (lcm) 구하기

 

 

# 핵심 개념

 

1. 최대공약수(Greatest Common Divisor, GCD)

 

최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

두개의 자연수를 1~N까지 나누어 공통되는 것을 찾아 그 중 max 값을 구하면 구할 순 있겠지만 높은 시간 복잡도를 가진다.

이에 최대공약수를 간단하게 풀 수 있는 유클리드 호제법을 사용한다.

유클리드 호제법: 
2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때,
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

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

 

 

아니면 파이썬에 내장되어 있는 import math 후 math.gcd를 사용할 수도 있다!

import math
math.gcd(a, b)

 

 

※ 만약 from ~ import 꼴로 사용한다면

math. 를 사용하지 않고 바로 함수를 호출할 수 있다!

 

from math import gcd

print(gcd(10,3)) # 1
print(gcd(12,4)) # 4

 

 

 

2. 최소공배수 (Least Common Multiple, LCM)

 

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

최소공배수는 다음과 같이 구할 수 있다.

 최소공배수 = 두 자연수의 곱 / 최대공약수 

 

import math
def lcm(a, b):
    return a*b // math.gcd(a, b)

 

 

 

# 문제 정답

 

def solution(n, m):
    answer = [gcd(n,m), lcm(n,m)]
    return answer

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

def lcm(a,b):
    return a*b // gcd(a,b)