Rust で解く 1 から max までのすべての自然数の最小公倍数

概要

『Project EulerのSmallest multipleをElixirで解く』という記事を読んで、 Rust ではどのように実装できるかやってみた。

（追記）@tatsuya6502 さんからご指摘を受け、コードを修正しました。

実装アプローチ

1. 再帰的アプローチ

元ネタのアルゴリズムを、ほぼそのまま Rust に移植した手法（一応、末尾再帰の形で実装したつもり。出来てなかったらコメントで教えてください）。
この手法のメリットは、関数プログラミング的なわかりやすさがあるところだ。デメリットとしては、 max の数が大きいとスタックオーバーフローを起こす可能性があることだ。 Rust では末尾再帰による最適化は保証されないので、速度面でもデメリットが発生する可能性がある。

stack

///a と b の最大公約数を求める
fn gcd(a: usize, b: usize) -> usize {
    if a % b == 0 {
        b
    } else {
        gcd(b, a % b)
    }
}

///ループ処理
fn solve(n: usize, lcm: usize, max: usize) -> usize {
    if n <= max {
        solve(n + 1, (n * lcm) / gcd(n, lcm), max)
    } else {
        lcm
    }
}

///1 から max までのすべての自然数の最小公倍数を求める
pub fn get_lcm(max: usize) -> usize {
    assert!(max > 2);
    solve(2, 1, max)
}

2. イテレータを使用したアプローチ

ループ処理に fold() を使用した手法。
この手法のメリットは、ループ部分ではスタックオーバーフローの危険がない¹ことである。デメリットとしては、ぱっと見では何をしているかわかりづらいところだ。

fold

///a と b の最大公約数を求める
fn gcd(a: usize, b: usize) -> usize {
    if a % b == 0 {
        b
    } else {
        gcd(b, a % b)
    }
}

///ループ処理
fn solve(max: usize) -> usize {
    (2..max + 1).fold(1, |lcm, n| {
        (n * lcm) / gcd(n, lcm)
    })
}

///1 から max までのすべての自然数の最小公倍数を求める
pub fn get_lcm(max: usize) -> usize {
    assert!(max > 2);
    solve(max)
}

3. 手続き的アプローチ

手続き的な手法。
この手法のメリットは、スタックオーバーフローの可能性がないことだ。デメリットとしては、可変な（ mut な）変数が必要なことだ。可変変数は意図しない場所での変更によるバグの温床になるため、 Rust ではデフォルトで変数は変更不可である。

procedural

///a と b の最大公約数を求める
fn gcd(a: usize, b: usize) -> usize {
    let (mut a, mut b) = if a < b {
        (b, a)
    } else {
        (a, b)
    };
    while b > 0 {
        let r = a % b;
        a = b;
        b = r;
    }

    a
}

///ループ処理
fn solve(max: usize) -> usize {
    let mut lcm = 1;
    for n in 2..max + 1 {
        lcm = (n * lcm) / gcd(n, lcm);
    }

    lcm
}

///1 から max までのすべての自然数の最小公倍数を求める
pub fn get_lcm(max: usize) -> usize {
    assert!(max > 2);
    solve(max)
}

最後に

Rust 的にはたぶん、最大公約数を求めるには手続き的手法を使い、ループ処理にはイテレータを使うのがいいんじゃないかと思う。

mix

///a と b の最大公約数を求める
fn gcd(a: usize, b: usize) -> usize {
    let (mut a, mut b) = if a < b {
        (b, a)
    } else {
        (a, b)
    };
    while b > 0 {
        let r = a % b;
        a = b;
        b = r;
    }

    a
}

///ループ処理
fn solve(max: usize) -> usize {
    (2..max + 1).fold(1, |lcm, n| {
        (n * lcm) / gcd(n, lcm)
    })
}

///1 から max までのすべての自然数の最小公倍数を求める
pub fn get_lcm(max: usize) -> usize {
    assert!(max > 2);
    solve(max)
}

以上、独断と偏見でコメントしてみた。

もし、もっとこんな方法があるよというアイディアや、ここはこうしたほうがいいというご意見があれば、コメントや編集リクエストで教えていただけると嬉しい。

1. わかりやすさを優先して gcd() では再帰的手法を使用しているので、この部分ではスタックオーバーフローの危険はある。 ↩