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

공약수

: 두 개 이상의 수에서 공통된 약수
ex) 12 의 약수 -> 1, 2, 3, 4, 6, 12
20의 약수 -> 1, 2, 4, 5, 10, 20
공통된 공약수 -> 1, 2, 4

최대공약수

: 공약수 중에 가장 큰 수를 최대공약수라 한다
ex) 12와 20의 최대공약수 공약수 1,2,4 중 가장 큰 4이다

• 소인수분해를 이용하면 최대공약수 및 공약수를 구할 수 있다
• 소수로 나숫셈을 하면 최대공약수를 구할 수 있다.

ex) 25, 115, 255 / 5 = 5 , 23, 51(더 나눌수있는게 없음)
최대공약수 5, 공약수 1, 6

두 개의 수를 입력하면 공약수와 최대공약수를 출력하는 코드를 작성

#num1 < num2
num1 = int(input("1보다 큰 정수 입력:"))
num2 = int(input("1보다 큰 정수 입력:"))

maxNum = 0
for i in range(1, num1+1):
   if num1 % i == 0 and num2 % i ==0:
    print("공약수{}".format(i))
    maxNum = i 

print("최대공약수{}".format(maxNum))

유클리드 호제법

: 유클리드 호제법을 이용해서 최대공약수를 구할 수 있다

• x, y의 최대공약수는 y,r(x%y)의 최대공약수와 같다

x % y = r
12 36 12
36 12 3
12 3 0
나머지가 0일 때까지 나눗셈하기
최대공약수 3