[Kotlin] 유클리드 호제법 알고리즘

유클리드 호제법이란?

• 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

 

기본 과정

예시로 32와 24의 최대공약수를 구하면,

1. 32는 24로 나누어 떨어지지 않기 때문에, 32를 24로 나눈 나머지를 구한다. => 8
2. 32는 8로 나누어 떨어진다.
3. 따라서 32와 24의 최대공약수는 8이다.

---

예제 코드1. 재귀 함수를 사용

package algorithm

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val number = bf.readLine().split(" ")

    val a = number[0].toInt()
    val b = number[1].toInt()

    println(gcd(a, b))
}

fun gcd(a: Int, b: Int): Int {
    return if (b==0) a
    else gcd(a, a%b)
}

 

2. 반복문을 사용

package algorithm

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val number = bf.readLine().split(" ")

    var a = number[0].toInt()
    var b = number[1].toInt()

    var c: Int
    while (b != 0) {
        c = a % b
        a = b
        b = c
    }
    println(a)
}

결과

---

연습 문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

https://www.acmicpc.net/problem/14490

14490번: 백대열