ユークリッド互除法で最大公約数を出力。(C#、Java、JavaScript、PHP、Python3、Ruby比較)

 2つの整数a、bがあり、aをbで割った余りをmとします。余りmを求めたら、aにbを、bに余りmを代入します。

 そして、上記の操作をbの値が0になるまで繰り返します。bが0になったときのaの値が、2つの整数a、bの最大公約数になります。

 これが「ユークリッドの互除法」と言われるものです。

 今回はこのユークリッドの互除法を用いて、標準入力から読み込んだ2つの整数a、bの最大公約数を求めて出力する処理を、C#、Java、JavaScript、PHP、Python3、Rubyの6言語で書いてみました。

 ユークリッド互除法により2つの整数の最大公約数を求める部分は、個別のメソッド(関数)の形式にしています。

C#
using System;
using System.Linq;

public class Sample{
    //ユークリッドの互除法で最大公約数を求める
    public static int euclidean(int num1, int num2){
        int a = num1;
        int b = num2;

        while (b != 0){
            int m = a % b;
            a = b;
            b = m;
        }

        return a;
    }

    public static void Main(){
        //標準入力から2つの数値を読み込む
        var num = Console.ReadLine().Trim().Split(' ').Select(x => int.Parse(x)).ToArray();

        最大公約数を出力
        System.Console.WriteLine(euclidean(num[0], num[1]));
    }
}
Java
import java.util.*;

public class Main {
    //ユークリッドの互除法で最大公約数を求める
    public static int euclidean(int num1, int num2){
        int a = num1;
        int b = num2;

        while (b != 0){
            int m = a % b;
            a = b;
            b = m;
        }

        return a;
    }

    public static void main(String[] args) throws Exception {
        //標準入力から2つの数値を読み込む
        Scanner scan = new Scanner(System.in);
        var line = Arrays.asList(scan.nextLine().trim().split(" "));

        var num = new ArrayList<Integer>();
        line.stream().map(x1 -> Integer.parseInt(x1)).forEach(y -> num.add(y));

        //最大公約数を出力
        System.out.println(euclidean(num.get(0), num.get(1)));
    }
}
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

reader.on('line', (line) => {
    lines.push(line);
});

reader.on('close', () => {
    //ユークリッドの互除法で最大公約数を求める
    function euclidean(n1, n2){
        var a = n1;
        var b = n2;

        while (b !==0){
            var m = a % b;
            a = b;
            b = m;
        }
        return a;
    }
    //標準入力から2つの数値を読み込む
    var num = lines[0].trim().split(' ').map(x => parseInt(x));

    //最大公約数を出力
    console.log(euclidean(num[0], num[1]));
});

 JavaScriptについては、下記の2つのフォームに半角で整数を記入して「送信」ボタンを押すことで、入力した2つの整数の最大公約数がブログ上に出力されるコンテンツも作りました。

数値1
数値2

 

 フォームに入力した2つの整数の最大公約数は、色の部分に表示されます。

 2つのフォームに数値が入力されていない状態で「送信」を押した場合は、「半角で数値を入力してください!」と表示されます。

 なお、半角の数字以外は符号も含めて削除されるため、正の整数だけが入力されるようになってます。

PHP
<?php
//#ユークリッドの互除法で最大公約数を求める
function euclidean($n1, $n2){
    $a = $n1;
    $b = $n2;

    while($b != 0){
        $m = $a % $b;
        $a = $b;
        $b = $m;
    }
    return $a;
}
////標準入力から2つの数値を読み込む
$num = explode(' ',fgets(STDIN));

//最大公約数を出力
echo euclidean($num[0], $num[1])."\n";
?>
Python3
#ユークリッドの互除法で最大公約数を求める
def euclidean(n1, n2):
    a = n1
    b = n2

    while b!=0 do
        m = a % b
        a = b
        b = m
    end

    return a

#標準入力から2つの数値を読み込む
num = list(map(int, input().rstrip().split(' ')))

#最大公約数を出力
print(euclidean(num[0], num[1]))
Ruby
#ユークリッドの互除法で最大公約数を求める
def euclidean(n1, n2)
    a = n1
    b = n2

    while b!=0 do
        m = a % b
        a = b
        b = m
    end

    return a
end

#標準入力から2つの数値を読み込む
num = gets.chomp.split(' ').map(&:to_i)

#最大公約数を出力
puts euclidean(num[0], num[1])

にほんブログ村 ゲームブログへ

スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする