Written by Amy
on 

최대공약수와 최소공배수

Greatest Common Divisor

뺄셈을 활용하기

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        if a > b {
            return gcd(a-b, b)
        } else {
            return gcd(a, b-a)
        }
    }
}

나눗셈을 활용하기

func gcd(_ m: Int, _ n: Int) -> Int {
  var a = 0
  var b = max(m, n)
  var r = min(m, n)

  while r != 0 {
    a = b
    b = r
    r = a % b
  }
  return b
}

재귀를 활용하기

func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

최대공약수를 활용한 최소공배수

func lcm(_ m: Int, _ n: Int) -> Int {
  return m*n / gcd(m, n)
}