配列の全ての要素の最大公約数を求める (Java 8, Python, PHP)

ちょっと調べた事をメモ。

まずはPython。itertools.reduce()とmath.gcd()を使って実質的にワンライナーで書けました。

import functools
import math

values = [290021904, 927964716, 826824516, 817140688]
gcd = functools.reduce(math.gcd, values)
print(gcd)

Java 8ではStream APIを使って実装してみます。どうしても冗長に見えてしまいますが、やっていることは同じです。

import java.math.BigInteger;
import java.util.stream.IntStream;

class GCD {
    public static void main(String args[]) {
        int gcd = IntStream.of(290021904, 927964716, 826824516, 817140688)
            .mapToObj(BigInteger::valueOf) // 型変換
            .reduce(BigInteger::gcd) // Python版のreduce(math.gcd)とほぼ同じですね
            .orElse(BigInteger.ZERO) // ↑はOptional<BigInteger>を返すので
            .intValue();

        System.out.println(gcd); // 92
    }
}

ちなみにPythonのmath.gcd()もJavaのBigInteger#gcd()も内部ではユークリッドの互除法を使っており自前で2つの整数の最大公約数を求めるような実装をする必要はありません。

2017-09-25 更新

コメントいただいたより簡潔な表記に改めました。また、結果も誤っていたので修正しました。

2017-09-25 追記

PHP版も書いてみました。PHPではGMP拡張のgmp_gcd関数がありますが、今回は自前でユークリッドの互除法を使った関数を実装。リストをreduceするやり方だと文法やシグネチャの違いぐらいしか差が出ませんね。

<?php
function gcd($a, $b) {
    return ($a % $b) ? gcd($b, $a % $b) : $b;
}
$values = [290021904, 927964716, 826824516, 817140688];
$gcd = array_reduce($values, 'gcd');
var_dump($gcd); // int(92)