최대공약수와 최소공배수
최대공약수
유클리드 호제법
주어진 두 수 사이의 최대공약수를 구하는 방법
주어진 두수 a와 b (a>b)를 나눈 나머지를 n 이라고 할때, (a%b = n )
n=0이면 b가 두 수의 최대공약수 이다.
n!=0이면
a에 b를 넣어주고, b에 n을 넣어주어, n=0이 될때까지 반복문을 돌려 최대공약수를 구한다.
1
2
3
4
5
6
7
8
9
10
int gcd(int a, int b){
int n;
do{
n= a%b;
if(n==0)
return b;
a=b;
b=n;
}while(1);
}
최소공배수
최대공약수 * (a/최대공약수) * (b/최대공약수) 이므로
a * b/최대공약수 이다 !!