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

 
Previous Post Perl 펄] 최소 공배수 구하기 함수; LCM; Least Common MultipleMP3 편집 프로그램 프리웨어; 불필요한 공백 삭제 자르기; 엠피쓰리 에디터(Editor)...Mathematica 매스매티카] 대분수를 가분수로 바꾸기, 입력 방법; To Improp...Mathematica 매스매티카] 가분수를 대분수로 변환 함수; To Mixed Fract...Mathematica 매스매티카] 분자 분모 구하기 함수, 분수 다루기; Get Numer...Mathematica 매스매티카] 소수점 나오게, 소수로 근사값 출력 방법; Decimal...윈도우 계산기] 밑이 2인 로그 값 구하기, 공식; Log Base Windows Calc...Mathematica 매스매티카 Log] 상용 로그, 자연 로그, 밑이 2인 로그 함수; ...Mathematica 매스매티카 텍스트 모드, 종료 핫키 끝내기 명령어; Text Vers...Mathematica 매스매티카] 복소수 사칙연산; 덧셈, 뺄셈, 곱셈, 나눗셈; Comp...

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

Wednesday, April 11, 2007

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

0 Comments:

Post a Comment

<< Home RSS 2.0 feed

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