【Rust】完全数をRustで求めてみる

あらまし

たまたまインターネットで完全数の魅力みたいなものを見たので、ちょっとはコンピュータを計算機らしい使い方しようと思い、Rustで求めてみました。

完全数とは

完全数とは、自分自身を除く正の約数の和と等しくなる自然数のことです。
出典：完全数とその魅力について－「博士の愛した数式」を観て、改めて数字の持つ奥深さに魅せられました－　|ニッセイ基礎研究所
要するに、ある数について正の約数の和が2倍になるか、もしくはその数引いたら等しくなるか、ということです。

ロジック

以下の処理を繰り返すだけ。
1. 約数の合計を求める
2. 元の数を減算し一致するか確認
3. 一致したら出力

なお、約数を求める際は、以下の効率的な解法を利用いたします。

あるの約数を列挙する際は、からまで以下の処理を繰り返す。
ならば、とを約数として保存する。

これは要するに、 が成立する場合をイメージしていただけるとわかりやすいかもしれません。
全部の数字に対する探索だとですが、この解法だとに削減できます。

ソースコード

fn divisors(n: usize) -> usize {
    let mut sum: usize = 0;
    for i in 1..=(f64::sqrt(n as f64) + 1e-9) as usize {
        if n % i == 0 {
            sum += i;
            if i != n / i {
                sum += n / i;
            }
        }
    }
    return sum;
}

fn main() {
    for i in 1.. 10000 {
        let x = divisors(i);
        if (x - i) == i {
            println!("It's perfect number: {}", i);
        }
    }
}

実装の際の参考にしたサイト：素数表を使わない約数の列挙 - Qiita

出力結果

$ rustc main.rs
$ time ./main
It's a perfect number: 6
It's a perfect number: 28
It's a perfect number: 496
It's a perfect number: 8128
./main  0.04s user 0.00s system 9% cpu 0.431 total

まとめ

簡単ですが、完全数をRustで求めてみました。普段だととりあえずC++で書いてみるかとなってしまうのですが、勉強中ということもあり練習がてらにサクッと書きました。 たまには数学のこういう問題をサクッと解くのも気分転換になって楽しいですね。

※ GitHubにもコードを上げています github.com