C언어] 최소공배수 구하기 함수; LCM; Least Common Multiple

#include <stdio.h>
#include <math.h>   // abs()
#include <stdlib.h> // _abs64()

int lcm(int a, int b);
unsigned __int64 lcm64(__int64 a, __int64 b); // 64비트 버전
int gcd(int a, int b);


int main(void) {

  printf("%d\n", lcm(4, 6) );    // 12
  printf("%d\n", lcm(21, 6) );   // 42
  printf("%d\n", lcm(-5, -4) );  // 20
  printf("%d\n", lcm(-9, 2) );   // 18
  printf("%d\n", lcm(0, 0) );    // 0

  // 세 숫자의 최소공배수 구하기
  printf("%d\n", lcm(45, lcm(120, 75)) );  // 1800

  // 네 숫자의 최소공배수 구하기
  printf("%d\n", lcm(112, lcm(113, lcm(114, 119))) );  // 12263664



  /* 가령 (51131, 215987, 24, 454452) 이런 숫자의 최소공배수는
     10037600660368488 (일경삼십칠조육천육억육천삼십육만팔천사백팔십팔) 이라는
     거대한 숫자가 나오기에, "unsigned __int64"로 반환하는
     lcm64 라는 함수를 별도로 만들었습니다.
  */
  printf("%I64u\n", lcm64(51131, lcm64(215987, lcm64(24, 454452))) );
  // 10037600660368488

  return 0;
}




// 최소 공배수 계산 함수
int lcm(int a, int b) {
  int gcd_value = gcd(a, b);

  if (gcd_value == 0) return 0;  // 인수가 둘다 0일 때의 에러 처리

  return abs( (a * b) / gcd_value );
}


// 최소 공배수 계산 함수: 64비트 버전
unsigned __int64 lcm64(__int64 a, __int64 b) {
  int gcd_value = gcd((int)a, (int)b);

  if (gcd_value == 0) return 0;  // 인수가 둘다 0일 때의 에러 처리

  return _abs64( (a * b) / gcd_value );
}


// 최대 공약수 계산 함수; 최소 공배수 계산에 사용됨
// (Euclidean Algorithm; Euclid's Algorithm)
int gcd(int a, int b) {

  while (b != 0) {
    int temp = a % b;
    a = b;
    b = temp;
  }

  return abs(a);
}