1.3 유클리드 알고리즘(최소공약수 찾기)

유클리드 알고리즘

 

임의의 두 정수 u,v 에 대해

1)  v 가 u보다 크다면 v와 u의 값을 바꾼다.

2)  u=u-v;

3)  u가 '0'이면 v가 최대 공약수

    '0'이 아니면 (1)로 돌아감

 

#include <iostream>
#include <vector>

using namespace std;
int get_gcd(int u, int v){
	int t;
	while(u!=0){
		if(v>u){
			t=u;
			u=v;
			v=t;
		}
		u=u-v;
	}
	return v;
}

int main(){
	cout<<get_gcd(10,10)<<endl;
	cout<<get_gcd(280,30)<<endl;
	cout<<get_gcd(12,3)<<endl;
	system("pause");
	return 0;
}

10
10
3

 

 

더 빠른 방법 ,,,

u 와 v의 값 차이가 클때 많은 뺄셈을 요구함

뺄셈의 결과는 나눗셈의 나머지를 구하는것

-GCD(u,v) = GCD(u%v,v) = GCD(v, u%v)

- u%v < v

 

임의의 두 정수 u,v에 대해

1) u가 0이 아니면

  (1,1) u= u%v

  (1,2) u와 v를 교환

  (1,3) (1)로 돌아감

(2) u가 0이면 v가 gcd

 

#include <iostream>
#include <vector>

using namespace std;
int get_gcd(int u, int v){
	int t;
	while(u!=0){
		if(v>u){
			t=u;
			u=v;
			v=t;
		}
		u=u%v;
	}
	return v;
}

int main(){
	cout<<get_gcd(10,10)<<endl;
	cout<<get_gcd(280,30)<<endl;
	cout<<get_gcd(12,3)<<endl;
	system("pause");
	return 0;
}

 

10
10
3