/*
 * 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;
}

저작자 표시 비영리 변경 금지
신고
Posted by sosal sosal

댓글을 달아 주세요