유클리드 호제법: 재귀

유클리드 호제법

2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

최대공약수 구하기

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
void gcd(int n,int m){
    int small,large;
    if(m == 0){printf("%d",n);return ;}
    small = (n>m?m:n);large = (n>m?n:m);
    gcd(small,large%small);
}
int main(){
    int n,m;scanf("%d %d",&n,&m);
    gcd(n,m);
}

 

최소공배수 구하기

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
int fuction_max(int n, int m){ return m? fuction_max(m,n%m):n;}
int fuction_min(int n, int m){return (n*m)/fuction_max(n,m);}
int main(){
   int n,m,rep;scanf("%d",&rep);getchar();
   for(int i=0;i<rep;i++){scanf("%d %d",&n,&m);getchar();printf("%d\n",fuction_min(n,m));}   
}