유클리드 호제법

개념

---

• 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나
• 호제법 = 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘

예시

---

1071과 1029의 최대공약수

 

1071%1029 = 42

1029%42 = 21

 

42는 21로 나누어 떨어짐

∴ 최대공약수 = 21

 

소스코드

---

public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }