mwultong Blog ... 프로그래밍 / 계산기

컴퓨터 엑셀 워드 포토샵 구글어스 WINDOWS JAVASCRIPT JAVA C++

 
Wednesday, April 11, 2007

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


C언어로, 지정한 숫자들의 최소공배수를 얻는 방법입니다. 아래 예제 소스의 lcm() 함수를 사용합니다. 그런데 최소공배수는 int 형의 범위를 넘는 거대한 숫자가 나오는 경우가 많기에, 64비트 버전 함수도 만들었습니다.

C에서, 최소 공배수 계산 예제 소스


소스 파일명: example.cpp
※ 아래 박스 클릭 후, 키보드 화살표 키로 좌우 스크롤 가능함
#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);
}



▶▶ C언어] 최대 공약수 구하기 함수; gcd Function, Greatest Common Divisor


최소공배수 계산기 (온라인 버전): ▶▶ 최소공배수 계산기; LCM 구하기 Calc




tag: cpp
C언어 | C/C++ (Visual C++)

0 Comments:

<< Home RSS 2.0 feed

구글 Google 에서 제공하는 무료 블로그 서비스인 블로거 Blogger 의 인터넷 주소는 www.blogger.com 입니다. Blogger 에 블로그를 만들면, blogspot.com 이라는 주소에 블로그가 생성됩니다.
블로그를 직접 방문하지 않고도 최신 게시물을 구독하려면 RSS 2.0 feed 주소를 리더기에 등록하시면 됩니다.
Previous Posts
Monthly Archives
Top