アルゴリズム学習−ユークリッドアルゴリズム(転がり相除去法)(c++実装)

ユークリッドアルゴリズム
ユークリッドアルゴリズムは転がり相除法とも呼ばれ、2つの整数の最大公約数を求めるアルゴリズムである.
もちろん最小公倍数を求めることもできます.
アルゴリズム実装
実はアルゴリズムの実現原理は、整数a bの2つがあって、毎回求めた1つの数字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
",gcd(a,b));
    return 0;
}

上はこれが求めた最大公約数です.実はこれによっても求められる最小公倍数です.
非再帰的実装
再帰呼び出しにスペースがかかるという友人がいることを考慮して、ここに非再帰方法を書きます.

int gcd(int a, int b){
    int temp = a;
    while(a%b != 0){
        a = b;
        b = temp%b;
        temp = a;
    }
    return b;
}

再帰的な方法は理解しやすいが,非再帰的な方法は確かに空間を節約しなければならない.大量のスタック操作は必要ありません.
最小公倍数
最小公倍数は、a bの積をそれらの2つの最大公約数で割ったものであり、それらの最小公倍数である.コードは次のとおりです.

int MinMultiple( int a, int b){
    return (a * b)/gcd(a, b);
}

これでいいです.