求最大公约数和最小公倍数

最大公约数采用“辗转相除法”计算。

C++实现：

#include <iostream>
using namespace std;

int gcd( int a, int b ); // 最大公约数
int lcm( int a, int b ); // 最小公倍数

int main()
{
    int a, b;
    cout << "Enter 2 integers: ";
    cin >> a >> b;

    cout << "The greatest common divisor is: " << gcd( a, b ) << endl;
    cout << "The least common multiple is: " << lcm( a, b ) << endl;

    return 0;
}

int gcd( int a, int b ) {
    int temp;
    if ( a < b ) { temp = a; a = b; b = temp; } // 交换位置
    while ( b != 0 ) {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

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

Python 实现：

#!/usr/bin/ python
# encoding: utf-8

# 最大公约数
def gcd( a, b ):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

# 最小公倍数
def lcm( a, b ):
    return a * b / gcd( a, b )

a = int( raw_input( "enter a: " ) )
b = int( raw_input( "enter b: " ) )
print "The greatest common divisor is %d\n"\
        "The least common multiple is %d\n"\
        % ( gcd( a, b ), lcm( a, b ) )