最大公約数、最小公倍数 | アルゴリズム [AOJ 0005][Ruby][Python][Java]

整数における最大公約数を求めるアルゴリズムは、『ユークリッドの互除法』が有名です。今回はこのアルゴリズムを使って、コードを書いていきます。

😸 Rubyコード

# 最大公約数
def gcd(a, b)
  a, b = b, a if a > b
  until a == 0
    a, b = b%a, a
  end
  return b
end

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

while gets do
  a, b = $_.chomp.split(' ').map(&:to_i)
  puts "#{gcd(a, b)} #{lcm(a, b)}"
end

👽 Pythonコード

# coding:utf-8
import sys

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

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

for s in sys.stdin:
  a, b = map(int,s.split())
  gcd_num = gcd(a, b)
  lcm_num = lcm(a, b)
  print "%d %d"%(gcd_num, lcm_num)

# output
# 2 24
# 10000000 150000000

🐡 Javaコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    while(true) {
      String tmp = br.readLine();
      if (tmp == null || tmp.isEmpty()) {
        break;
      }
      List list = Arrays.asList(tmp.split(" ")).stream().map(i -> Long.parseLong(i)).sorted().collect(Collectors.toList());
      long koyakusu = getKoyakusu(list.get(0), list.get(1));
      long kobaisu = getKobaisu(list.get(0), list.get(1));
      System.out.printf("%d %d\n", koyakusu, kobaisu);
    }
  }

  // 公約数の取得
  private static long getKoyakusu(long a, long b) {
    long candidate = a;
    while (b % a != 0) {
      candidate = b % a;
      b = a;
      a = candidate;
    }
    return candidate;
  }

  // 公倍数の取得
  private static long getKobaisu(long a, long b) {
    return (a * b) / getKoyakusu(a, b);
  }
}

// output
// 2 24
// 10000000 150000000