Euclidean algorithm (유클리드 호제법)

1. 유클리드 호제법이란?

---

 유클리드 알고리즘은 2개의 자연수의 최대 공약수를 구하는 알고리즘이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

 

2. 예시

---

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

      

      

      

    
    

      <code />
    
    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 ＋ 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2 ＋ 0

따라서, 최대공약수는 36이다.

 

2.1. By Kotlin

      

      

      

    
    

      <kotlin />
    
fun gcd(p: Int, q: Int): Int {
	if(q == 0) return p
    return gcd(q, p % q)
}

2.2.  

2.3. 최소 공배수 구하기

 두 수의 최소 공배수는 p * q / gcd(p, q)의 관계가 성립한다.

 

      

      

      

    
    

      <kotlin />
    
fun lcm(p: Int, q: Int): Int {
    return p * q / gcd(p, q)
}

 

3. Reference

유클리드 호제법 - 위키백과, 우리 모두의 백과사전