歐幾裡得算法也叫輾轉相除法,是求兩個整數最大公約數的算法。
當然也可以求最小公倍數。
其實算法的實現原理就是,有整數a b
兩個,每次求的一個數字r = a % b
,然後把b
放到a
的位置,把r
放到b
的位置,遞歸調用。
就是gcd(a, b) { return gcd(b, a%b); }
這個樣子的。
結束條件是當 a%b == 0
的時候停止。
//
// main.cpp
// Euclidean
//
// Created by Alps on 15/3/28.
// Copyright (c) 2015年 chen. All rights reserved.
//
#include
using namespace std;
int gcd(int a, int b){
if (a%b == 0) {
return b;
}
return gcd(b, a%b);
}
int main(int argc, const char * argv[]) {
int a = 14, b = 18;
printf("%d\n",gcd(a,b));
return 0;
}
上面這個就是求的最大公約數的。其實通過這個也能求的最小公倍數。
最小公倍數,就是a b
的乘積除以它們兩個的最大公約數,就是它們的最小公倍數。代碼如下:
int MinMultiple( int a, int b){
return (a * b)/gcd(a, b);
}
這樣子就可以了。