最大公約数、最小公倍数 | アルゴリズム [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

🤔 GitHubリポジトリ

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

morizyun/aoj-ruby-python - GitHub

🖥 VULTRおすすめ

VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍