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

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

 
Friday, March 16, 2007

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


2개의 정수의 최대공약수를 구하는 소스입니다. 아래의 gcd() 함수를 중복하여 사용하면, 여러 개의 정수의 최대 공약수도 구할 수 있습니다.

최대공약수란 다음과 같습니다:

둘 이상의 정수들이 있고, 그 정수들을 어떤 숫자로 동시에 나누었을 때, 나머지가 없이 딱 나누어 떨어지는 숫자들이 몇 개 있을 것입니다. 그 숫자들 중에서 가장 큰 양수를 최대공약수라고 합니다. 분수의 약분에 사용됩니다.

예를 들어, 12와 18의 최대 공약수는 6인데,
6으로 12와 18을 나누면 나머지가 없이 딱 떨어집니다.

6은 {1, 2, 3, 6} 으로 나누어 떨어지고
18은 {1, 2, 3, 6, 9, 18} 로 나누어 떨어지지만

공통되는 약수 즉 공약수 중에서 가장 큰 숫자는 6입니다.

C에서, 최대공약수 계산 출력 소스


소스 파일명: example.cpp
※ 아래 박스 클릭 후, 키보드 화살표 키로 좌우 스크롤 가능함
#include <stdio.h>
#include <math.h> // abs()

int gcd(int a, int b);


int main(void) {

  printf("%d\n", gcd(12, 18));
  // 6

  printf("%d\n", gcd(5154, 3435));
  // 3

  printf("%d\n", gcd(0, 0));
  // 0
  // 이 경우는 0으로 정의되어 있습니다.

  printf("%d\n", gcd(1, 0));
  // 1
  // 이 경우에는 1이 맞습니다.

  printf("%d\n", gcd(0, 12));
  // 12
  // 이 경우에는 12가 맞습니다.

  printf("%d\n", gcd(13, 12));
  // 1
  // 공약수가 1밖에 없는 '서로소(Relatively Prime; Coprime)'

  printf("%d\n", gcd(-42, -56));
  // 14
  // 최대공약수는 항상 양수임

  // 세 가지 수의 최대공약수 구하기
  printf("%d\n", gcd(gcd(42, 12), 48));
  // 6


  return 0;
}




// 최대 공약수 계산 함수
// (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++를 설치한 경우에는 도스창(정식명칭은 '명령프롬프트')에서
cl example.cpp
이렇게 컴파일하고

example.exe
이렇게 실행하면 됩니다.


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


최대공약수 계산기 (온라인 버전): ▶▶ 최대공약수 계산기; GCD 구하기 Calculator




tag: cpp
C언어 | C/C++ (Visual C++)
tag: study
학습 | Study

0 Comments:

<< Home RSS 2.0 feed

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