최대 공약수

두 정수 A와 B가 있을때 A와 B를 소인수 분해가 가능하다. 그때 각 수는 약수들의 곱으로 표현되는데, A와B가 가진 공통의 약수들중 최대 인 수를 의미함.

예를 들어 100과 15를 보면 2255와 35 이므로 최대 공약수는 5다.

중학교 과정을 거치면 다들 개념정도는 알리라 믿는다.

구하는 법

O(n)

a,b 
target = None
for i in range(min(a,b),0,-1):
	if a % i == 0 and b % i == 0 :
    	target = i 
        break
print(target)

말그대로 무식하게 1씩 빼가면서 구하는 방법이 있다. 최대 공약수는 아무리 커도 a와 b 둘 중 작은 수 이상은 될 수 없으니 둘 중 작은 값으로 설정해줌.

이 방식의 최대 단점은 min(a,b) 값이 커질수록 느려진다는 것이며, 고난도 알고리즘 문제에서 n 값이 100,000 1,000,000 이상 되는 경우도 종종 있어 이 방식으로 구하면 보통 늦는 경우가 많다.

유클리드 호제법

개념 참고

요약하자면 아래와 같다.

정수 a,b에 대해서 a >= b 가 만족한다고 할때, r은 a를 b로 나눈 나머지라고 하자. 이때 a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

코드로 옮기면 아래와 같다.

def gcd(a,b):
	# 몇몇 문제에선 a >= b를 보장하지 않는다. 
    # 따라서 그걸 처리하기 위한 코드
    if a < b :
        a,b = b,a
        
    # r 구하기
    r = a % b
    
    # r == 0, a가 b의 배수라면, b 반환
    if r == 0:
        return b 
    # 아니라면 유클리드 호제법으로 진행.
    else:
        return gcd(b,r)