유클리드 호제법

코딩테스트를 공부하다가 최대공약수 혹은 공약수 최소 공배수를 구하는 문제를 많이 접하게 되어

유클리드 호제법을 꼭 알고 가야겠다라는 생각이 들었다

 

유클리드 호제법이란,

숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수와 같다는 것을 의미한다.

 

따라서 최대 공약수를 구하는 코드는 이렇게 된다.

최대공약수

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

최소 공부새는 a, b의 곱을 최대 공약수로 나누면 알 수 있다.

최소공배수

def lcm(a, b):
    return a * b / gcd(a, b)

공약수

공약수는 최대 공약수의 약수를 구하면 된다.

따라서 약수를 구하는 법을 알아보려고 한다.

약수를 구하는 방법은 몇 가지 있지만 그 중에서 제일 빠르게 구할 수 있는 방법을 알아보았다.

import sys
input = sys.stdin.readline

n = int(input())

d = set()
d.add(n)
for i in range(2, int(n**0.5)+1):
	if n%i == 0:
		d.add(i)
		if i!=n//i:
			d.add(n//i)

print(*d)

for 문을 이용해서 입력받은 수의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 입력받은 수로 나누면 알 수 있다.

또한 중복 값을 제거해주기 위해 set으로 바꿔주었다.

 

이렇게 이번에는 최대공약수, 최소공배수, 공약수를 구하는 알고리즘을 알아보았다.