数学タグ付いてるけど算数。

連除法

小学4年生で最大公約数・最小公倍数を習うのだが、その際の「やりかた」に連除法（すだれ算とも）というものがあると知った。

やりかた

最大公約数（GCD）

整数の組に共通する約数がある場合に約していき、除数をすべて乗算して求める

最小公倍数（LCM）

整数の組に2つ以上共通する約数がある場合に約していき、除数とあまりをすべて乗算して求める

よくあるGCD、LCM

もちろん、ユークリッドの互除法で簡単にできる。整数の組が2個より多い場合でも $gcd(a,b,c) = gcd(gcd(a,b),c)$ で解ける。

public int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}

public int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

再実装してみる

しかしながら、娘が Scratch で再現可能なことが目的なので、ひとまず Java で素組みしてみる。
ソース

整数の組を素数で約してみる

GCDとLCMのときでは約するやり方が異なるので、Predicate を入れ替えている。Java でも関数を渡せるね！

Integer primeFactory(List<Integer> intList) {
    Predicate<Integer> op = mode.equals(Mode.GCD) ? factoryAll(intList) : factoryMulti(intList);
    return primeList.stream().filter(op).findFirst().orElse(1);
}

static Predicate<Integer> factoryAll(List<Integer> intList) {
    return i -> intList.stream().allMatch(isDivisable(i));
}

static Predicate<Integer> factoryMulti(List<Integer> intList) {
    return i -> intList.stream().filter(isDivisable(i)).count() > 1;
}

約せたら次の段に移る

元の整数の組を約数で割った、新しい整数の組を生成する。UnaryOperator で単項演算を渡している。LCMのため割り切れない場合は元の整数を返す。

static List<Integer> divideList(Integer divisor, List<Integer> intList) {
    return intList.stream().map(divide(divisor)).collect(Collectors.toList());
}

static UnaryOperator<Integer> divide(Integer divisor) {
    return i -> (i % divisor) == 0 ? i / divisor : i;
}

最終的に対象をすべて乗算する

Integer getGCD() {
    return reduceDivisor();
}
Integer getLCM() {
    return getLastValue().stream().reduce(1, (x, y) -> x * y) * reduceDivisor();
}
Integer reduceDivisor() {
    return stack.stream().map(p -> p.getKey()).reduce(1, (x, y) -> x * y);
}

あとがき

ステップ三つだけど Scratch で組むのはしんどそうなので保留中。素数導出はいずれ。

小学4年生で学ぶ連除法について

連除法