[파이썬, Python] 최대공약수(GCD)

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

• 공약수(common divisor)란 두 수 이상의 여러 수의 공통된 약수를 의미
• 최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킴
• 최대공약수가 1이면 두 수는 서로소(coprime) 관계

출처 : TCP school

 

 

기본적인 방법

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

 

 

유클리드 호제법 사용

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

# or

def gcd(a, b):
    if a % b == 0:
        return b
    elif b == 0:
        return a
    else:
        return gcd(b, a % b)

 

 

파이썬 math 라이브러리 사용

import math
a, b = 10, 15
math.gcd(a, b)  # 5

 

 

 

 

 

 

 

 

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

코딩교육 티씨피스쿨

https://bloowhale.tistory.com/103

[Python] 최소공배수와 최대공약수

https://slowsure.tistory.com/128

[Python/파이썬]최소공배수 & 최대공약수 & 약수