辗转相除法

　

辗转相除法

采用递归实现:

#include <iOStream>
#include <algorithm>
using namespace std;

int gcd(int a,int b){
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}

int main(){
	
	cout<<gcd(4,2)<<endl;
	cout<<gcd(2,4)<<endl;
	return 0;
}

采用循环实现:

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a,int b){
	int m=a,n=b,r;
	if(m<n){
		int temp = m;
		m = n;
		n = temp;
	}
	r = m % n;
	while(r){
		m = n;
		n = r;
		r = m % n; 
	}
	return n;
}

int main(){
	
	cout<<gcd(4,2)<<endl;
	cout<<gcd(2,4)<<endl;
	return 0;
}

相关阅读

【递归】辗转相除法

  辗转相除法; 又名欧几里德算法（Euclidean algorithm），是求最大公约数的算法 原理：两个整数的最大公约数等于其中较小的数和两数