(Python) 최대 공약수, 최소 공배수 구현

  • by

최대 공약수

GCD(Greatest Common Divisor)

둘 이상의 공통 약수 중 최대 수


http://www.tcpschool.com/codingmath/common

위의 경우 72와 90의 최대 공약수는 18입니다.

gcd=1이면 서로 소관계에 있다고 표현한다.

인기글

최대 공배수

LCM(Least Common Multiple)

둘 이상의 숫자의 공통 배수 중 최소 수


http://www.tcpschool.com/codingmath/common

위의 경우 24, 30의 최대 공배수는 120이 나온다.

구현

최소 공약수

def solution(a, b):
    for i in range(min(a,b),0,-1):
        if a%i == 0 and b%i == 0:
            return i

최대 공배수

def solution(a, b):
    for i in range(max(a,b),(a*b)+1):
        if i%a == 0 and i%b == 0:
            return i

요구하는 수가 많은 경우는, arguments 를 사용해 list 로서 받아, 코드를 변경해 사용하면 된다.

Math

math 라이브러리를 사용하여 최대 공약수 얻기

import math

#최소공약수
print(math.gcd(10,20))
print(math.gcd(15,20,30))

#최대공약수
print(math.lcm(10,20))
print(math.lcm(15,20,30))