Programing/C- programing

최대공약수 최소공배수 gcd lcm 소스코드

sosal 2011. 2. 12. 12:58
반응형

/*
 * made by so_sal
 * http://sosal.tistory.com/
 */

정수론 수업시간에 배웠던 호제법으로 옛날에 만들어놓은 소스입니다.
최근 더블릿 시작했는데, 3계단에서 많이 쓰이길래 올려봅니다.

gcd : 최대공약수
lcm : 최소공배수

#include<stdio.h>
#include<iostream>
#include<cstring>

using namespace std;

int gcd(int a,int b){
   printf("a::%10d, b::%10d, a\%b::%10d\n",a,b,a%b);
    if(a%b == 0){
        return b;
    }
    return gcd(b,a%b); //호제법
}

int lcm(int a,int b){
    return a*b/gcd(a,b);
}

int main(void){
    int a,b;
    cin>>a>>b;

    printf("gcd를 구하는 과정 .. \n");
    int Vgcd = gcd(a,b);
    int Vlcm = a*b/Vgcd;

    printf("gcd is :: %d\n",Vgcd);
    printf("lcm is :: %d\n",Vlcm);

    return 0;
}

'Programing > C- programing' 카테고리의 다른 글

화일처리 - MovieLensData 통계 소스  (0) 2011.05.20
소수 판별 프로그램 소스  (2) 2011.02.12
C++ - 포함과 상속  (2) 2010.12.28
C++ : Const 함수 속성  (0) 2010.09.14
C++ - inline function 인라인 함수  (0) 2010.09.14