최소공배수

유클리드 호제법으로 표현

큰 수 = 최대공약수 * 첫번째 몫 + r1

작은 수 = 최대공약수 * 두번째 몫 + r2

최소공배수 = 최대공약수 * 첫번째 몫 * 두번째 몫

변수를 보고 이해할 수 있게 변형

big = gcd * div1 + residue1

small = gcd * div2 + residue2

lcd = gcd * div1 * div2

추가 개념 참조

최대공약수 구하는 방법

big = int(input("big = "))

small = int(input("small = "))



# 최대공약수 구하자

def gcd(big,small):

    # 순서 맞추자

    if big < small:

        temp = big

        big = small

        small = temp

    # 최대공약수 구하자

    while small != 0:

        residue = big % small

        big = small

        small = residue

    return big

# 최소공배수 구하기

def lcb(big,small):

    # lcd = gcd * div1 * div2

    return gcd(big,small) * (big / gcd(big,small)) * (small / gcd(big,small)) 



print("The lcb is %d." %(lcb(big,small)))

코드 돌리기

22과 3의 최대공약수 구하자

big = 22

small = 3

The lcb is 66.

25와 35의 최대공약수 구하자

big = 25

small = 35

The lcb is 175.