Volume0: 0005

最大公約数と最小公倍数 | Aizu Online Judge

最大公約数と最小公倍数を求める問題です。

整数 に対して、最大公約数 と は、 という関係があります。

最大公約数は、ユークリッドの互除法を使って求めることができます。

C++

#include <iostream>
using namespace std;

long a, b, gcd, lcm;

// ユークリッドの互除法より最大公約数を求める
long euclideanAlgorithm(long a, long b)
{
    // a > b になるように a と b を入れ替える
    if (a < b) swap(a, b);

    // 剰余が0になった時の除数が a と b の最大公約数
    if (b == 0) return a;

    // 剰余が0になるまで、剰余を求める計算を繰り返す
    return euclideanAlgorithm(b, a % b);
}

int main()
{
    while (cin >> a >> b) {
        gcd = euclideanAlgorithm(a, b);  // 最大公約数
        lcm = a * b / gcd;               // 最小公倍数
        cout << gcd << " " << lcm << endl;
    }

    return 0;
}

Python

math.gcd(a, b)は、aとbの最大公約数を返します。

# coding: utf-8

import math

while True:
    try:
        a, b = [int(i) for i in input().split()]

        gcd = math.gcd(a, b)  # 最大公約数
        lcm = a * b // gcd    # 最小公倍数

        print(f'{gcd} {lcm}')
    except EOFError:
        break

Ruby

Integer#gcdとInteger#lcmを利用し、最大公約数と最小公倍数を求めることができます。

# coding: utf-8

while line = gets
  a, b = line.chomp.split.map(&:to_i)

  gcd = a.gcd(b)  # 最大公約数
  lcm = a.lcm(b)  # 最小公倍数

  puts %Q!#{gcd} #{lcm}!
end

%Q!STRING!は、ダブルクォート文字列と同等です。