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

今回は、『最大公約数と最小公倍数』に関する問題です。

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

(09/03 20:55) 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.InputStreamReader;
import java.lang.Exception;
import java.lang.String;
import java.lang.System;
public class Main {
public static void main(String[] a) throws Exception {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
long num[] = new long[2];
long gcd, lcm;
String numStr[] = new String[2];
String str;
while((str = r.readLine()) != null) {
numStr = str.split(" ");
for(int i = 0; i < numStr.length; i++) {
num[i] = Long.parseLong(numStr[i]);
}
gcd = getGCD(num[0], num[1]);
lcm = getLCM(num[0], num[1]);
System.out.printf("%d %d\n", gcd, lcm);
}
}
// a, bの最大公約数を求める
private static long getGCD(long a, long b) {
if(a > b) {
long tmp;
tmp = a;
a = b;
b = tmp;
}
while(a != 0) {
long tmp = a;
a = b%a;
b = tmp;
}
return b;
}
// a, bの最小公倍数を求める
private static long getLCM(long a, long b) {
return (a * b)/getGCD(a, b);
}
}
# output
# 2 24
# 10000000 150000000

🏈 GitHubリポジトリ

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/Python/JavaでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあればぜひ^^

morizyun/aoj-ruby-python - GitHub

📚 おすすめの書籍

💩 欲しいものリスト公開しました