[We-Co] 최대 공약수 , 최소 공배수 - Python

안녕하세요. 위기의 코딩맨입니다.

오늘은 코딩 문제에서 가끔 사용되는 최대 공약수, 최소 공배수 구하는 방법을 알아보도록 하겠습니다.

[ 최대 공약수 ]

유클리드 알고리즘을 사용하여 최대 공약수를 구하는 코드입니다.

입력 값 A, B 를 받아 나눠 % 연산 후 몫이 아닌 나머지를 구합니다.

 

 

def Max_Value(A, B):

    while B != 0:

        R = A % B 

        A = B

        B = R

    return A

결과를 확인해 보면

Max_Value(12,3) 

Max_Value(48,60)

 

 

결과

[ 최소 공배수 ]

최소 공배수 구하는 방법은 주어진 A,B의 값을 구하고 최대 공약수를 나눠주면 값을 쉽게 구할 수 있습니다.

// 연산자는 나누기 연산 후 소수점 이하의 수를 버리고, 정수 부분의 수를 남겨주는 연산자 입니다.

 

def Min_Value(A,B):

    A = A * B // Max_Value(A,B)

    return A

결과를 확인해 보면

Min_Value(10,30)

Min_Value(6,25)

결과 2

 

오늘은 간단하게 최대 공약수, 최소 공배수 알고리즘을 알아보았습니다.

앞으로 Python을 이용한 알고리즘 공부를 해보겠습니다.