최대공약수, 최대공배수 구하는 함수 - swift

 

 

최대 공약수 ( Greatest Common Divisor )

주어진 숫자를 소인수 분해해서 나오는 수들을 '약수'라고 한다.

예를 들어

12의 약수는 [1, 2, 3, 4, 6, 12] 이다.

18의 약수는 [1, 2, 3, 6, 9, 18] 이다.

 

여기서 공통된 약수들을 '공약수' 라고 부른다.

12, 18의 공약수는 [1, 2, 3, 6] 이다.

 

공약수 중에 가장 큰 수를 '최대 공약수'라고 부른다.

(위의 예시에서는 공약수 중에 가장 큰 수가 6이므로 최대공약수는 6 이다.)

 

최대 공약수는 다음과 같이 구한다.

func GCD(_ min: Int, _ max: Int) -> Int {
  let rem = min % max
  
  if rem == 0 { // 나머지가 0인 수. 즉, 약수를 의미한다.
    return max
  } else {
    return GCD(max, rem)
  }
}

가장 큰 공약수가 나올 수 있는 경우는 둘 중 큰 수 자기 자신이므로 

약수 중 가장 큰수가 나올 때까지 GCD를 재귀 호출하여 최대공약수를 구한다.

 

+ 최대공약수를 알면 공약수를 구하기 쉬워진다. 최대공약수의 약수가 공약수이기 때문이다.

+ 1을 제외하고 서로 공통된 약수가 없는 수를 '서로소' 라고 한다. 따라서 최대공약수가 1이라면 서로소이다.

 

 

 

 

 

 최소 공배수 ( Least Common Multiple )

두 자연수의 배수를 쭉 나열한다고 생각해보자.

예를 들어

2의 배수는 2, 4, 6, 8, 10, 12, 14, 16, 18, ... 이다.

3의 배수는 3, 6, 9, 12, 15, 18, 21, 24, 27, ... 이다.

 

2와 3의 배수들 중에 둘이 공통적으로 가지고 있는 수를 '공배수' 라고 한다.

여기서 공배수는 6, 12, 18, ... 이다.

이 공배수 중 가장 작은 수를 '최소 공배수'라고 한다. 

(공배수중 가장 작은 수가 6이므로 최소공배수는 6 이다.)

 

최소공배수는 다음과 같이 구한다.

func LCM(_ a: Int, _ b: Int) -> Int {
  return a * b / GCD(a, b)
}

 

최소공배수는 두 자연수의 곱 / 최대공약수 이다.

 

+ 최대공약수와 마찬가지로 최소공배수를 알면 공배수를 구하기 쉬워진다.

최소공배수의 배수가 공배수이기 때문이다.

 

 

 

 

 

공약수 리스트 구하기

func GCD_list(_ min: Int, _ max: Int) -> [Int] {
  var divisors: [Int] = []
  let gcd = GCD(min, max)
  
  for i in 1...gcd {
    if gcd % i == 0 {
      divisors.append(i)
    }
  }
  return divisors
}

 

+ 최대공약수 * 최소공배수는 두 자연수의 곱과 같다.

ex.

4, 6의 최대공약수 = 2

4, 6의 최소공배수 = 12

 

최대공약수 * 최소공배수 = 2 * 12 = 24

두 자연수의 곱 = 4 * 6 = 24

 

 

 

 

 

 

틀린부분이 있거나, 더 좋은 방법이 있다면 댓글로 남겨주세요! 
🌈댓글은 언제나 환영입니다🙏🏻