[파이썬/python] 유클리드 호제법으로 최대공약수&최소공배수 구하기 (+관련 라이브러리)

 

 

<최대공약수>

 

반복문

def Euclidean(a, b):
    while b != 0:
        a, b = b, a%b
    return a

재귀문

def Euclidean(a, b):
    r = b % a
    if r == 0:
        return a
    return Euclidean(r, a)

 

결과

6과 10의 최대공약수는 2

 

10과 30의 최대공약수는 10

 

 

 

---

 

<최소공배수>

def Euclidean(a, b):
    aa,bb = a,b
    while b != 0:
        a, b = b, a%b
    return aa*bb//a

 

결과

 

최소공배수 구하는 공식은 두 수를 곱한 수에다 두 수의 최대공약수를 나눠주면 된다.

따라서 먼저 두 수의 최대공약수를 유클리드호제법을 이용하여 구한 다음, 두 수의 곱에 나눠주면 된다.

6과 10의 최대공약수는 2, 6*10//2는 30

따라서 6과 10의 최소공배수는 30

 

 

 

 

---

 

+관련 파이썬 라이브러리

import math
math.lcm(A, B) #최소공배수

import math
math.gcd(A, B) #최대공약수