酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

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

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

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

(09/03 20:55) Java 追加しました!


最大公約数、最小公倍数のRubyサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 最大公約数
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サンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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のサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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

Aizu Online Judgeのサンプルソース

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

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

おすすめの書籍