📝이론

공약수

2개 이상의 수에서 공통된 약수
ex. 12, 20의 공약수 = 1, 2, 4

최대공약수

공약수 중 가장 큰 수
ex. 12, 20의 최대공약수 = 4

---

💻 파이썬

최대공약수

🏷️조건(1)
for i in range(1, (num1 +1)):

• 우리는 공약수를 구하려고 함
• 따라서 num1이 num2보다 작다고 할때, num1 보다 작은 숫자 중에서 확인하면 됨

🏷️조건(2)
if num1 % i == 0 and num2 % i ==0:
두 수 모두 나머지가 0일 때 공약수를 구할 수 있음

---

최대공약수 (응용)

3개 수의 공약수, 최대공약수 구하기

---

📌유클리드 호제법 _ [최대공약수] 구하기!

x,y의 최대공약수 == y, r(x % y,나눴을 때의 나머지)의 최대공약수

• x,y의 최대공약수는 y, r(x % y)의 최대공약수와 같다.
• 나머지가 0이 나오는 시점의
• 2번째 수가 최대공약수 가 된다.

temp1 = num1; temp2 = num2

• temp1 = X 줄
• temp2 = Y 줄

temp1 = temp

• temp1 : 최대 공약수
• temp = '34'번 줄과 같이 temp2의 값을 가져옴

---

참고/출처 제로베이스 데이터 스쿨