Rustでイテレータを組み合わせて素因数分解してみる

たぶん実用性皆無

なにぶん勉強し始めたばかりなので、 もっとカッチョイイ書き方があったら、ぜひ教えて！

準備.素数イテレータ

まずは、素数をイテレータで生成してみる

生成済の素数列を状態として持っておいて、next()が呼ばれるたびに、

[]の場合 => 素数列を[2]にする
[2]の場合 => 素数列を[2,3]にする
[2,3,...n]の場合 => n+2から+2ずつ走査して、
生成済の素数列の全要素で割り切れないもの(=np)を探して素数列に加える

素数列の末尾を返す

とすれば良さそう

「全要素で割り切れないもの」については、検査する数の平方根までで打ち切って良い

というわけで実験

    for p in (0..).scan(Vec::<u64>::new(), |state, _| { 
        let np = match state.last() {
            None     => Some(2),
            Some(&2) => Some(3),
            Some(&n) => (1..).map(|x| x*2+n)
                             .find(|&x| state.iter()
                                             .take_while(|&p| p*p <= x)
                                             .all(|&p| x % p != 0))
        };
        state.push(np.unwrap());
        np
    }).take(10) {
        println!("{}", p);
    }

↓結果

2
3
5
7
11
13
17
19
23
29

おお、良さそう

状態変数に入れる値(Vec::<64>::new())は自動でミュータブルになるのかしら？

let mut state = Vec::<64>::new() みたいな？

割るぜ！.素因数分解イテレータ

これをもとに、素因数分解してみる

    let n = 179046;
    for f in (0..).scan((n, Vec::<u64>::new()), |state, _| {
        match match (state.0, state.1.last()) {
            (1, _)        => None,
            (_, None)     => { state.1.push(2); Some(2) },
            (n, Some(&2)) if n % 2 != 0 => { state.1.push(3); Some(3) }
            (_, Some(&p)) => Some(p)
        } {
            None => None,
            Some(f) if state.0 % f == 0 => {
                state.0 /= f;
                Some(f)
            },
            _ => {
                let t = state.0;
                let f = (0..).scan(&mut state.1, |v, _| {
                    let lastp = *v.last().unwrap();
                    let np = (1..).map(|x| x*2 + lastp)
                                  .find(|&x| v.iter()
                                              .take_while(|&pv| pv * pv <= x)
                                              .all(|&pv| x % pv != 0));
                    v.push(np.unwrap());
                    np
                }).find(|&x| t % x == 0 );

                state.0 /= f.unwrap();
                f
            }
        }
    }
    ) {
        println!("{}", f);
    }

ううむ、変態的だ（汗）

結果

2
3
3
7
7
7
29

できた！

外側のscanで(素因数分解する数, それまでに消費した素数列)を状態変数として、
素因数(f)を見つけるごとに、素因数分解する数を割って(state.0 /= f)、
素因数(Some(f))をイテレータの出力にしている

(0..)は素因数分解が終わるまでループさせるためのもの
state.0が1になったら、Noneを出力してループを終了させる

scanの関数はmatch二段掛け（汗）

一段目は、素因数分解の終了判定と、素数列の末尾から素因数の候補を生成する
素数列が空の場合は、2を格納して2を候補とする
素数列が2だけで目的の数を2で割れない場合は、3を格納して3を候補とする
（2 -> 3だけ、+2で生成できないため）
それ以外の場合は、とりあえず素数列の末尾を候補とする

二段目のmatchで、
候補にした数で割れるならそのまま出力、
割れないならば割れる数が見つかるまで素数を生成する

14行目からのマッチが素数列を更新しながら素因数を探しているところ
素数列を生成していって(let np=...)、findで目的の数を割れるものを探している
内側のscanの状態にしている素数列は外側のscanの状態変数をミュータブル参照で
借用しないとなので所有・参照関係を解決するのがちょっと大変
あまり褒められたやり方じゃあない気も？

23行目は直接state.0を書きたいけれど、
scanでstate.1をミュータブル参照してしまっているのでできない
仕方がないので別の名前に移し替えている

なんとか動いているけれど、まだ勘所がよくわからないので
コンパイラのエラーメッセージとにらめっこでご機嫌を伺ってる感

タグ：RUST