[素因数分解] Trial Division / 試し割り法

こんちくわ。試し割り法は素因数分解の一番愚直なアルゴリズムです。

この解説をします。

Method

ある合成数$N$の素因数$p$を求めたい時に、このアルゴリズムは小さい数から割り切れるかどうかを調べていきます。¹

小さい数から調べるので、この方法で見つかるであろう$p$は$N$の素因数の中でも最小のものであるはずですよね。$p$が$N$の最小の素因数なら、

$2 \le p \le \lfloor \sqrt{N} \rfloor $

であるので²、この範囲を調べて見つからなければその数は素数ということになります³。

Implementation in C++

vector<ll> trial_division(const ll& n) {
    ll result = n;
    for (ll i = 2, m = (ll)sqrt(n); i <= m; ++i)
    {
        if (n % i == 0) {
            result = i;
            break;
        }
    }

    if (result == n) {
        return { n };
    } else {
        vector<ll> v1 = { result };
        vector<ll> v2 = trial_division(n / result);
        v1.insert(v1.end(), v2.begin(), v2.end());
        return v1;
    }
}

Implementation in Rust

fn trivial_division(n: u64) -> Vec<u64> {
    let mut result = n;
    for i in 2..((n as f64).sqrt() as u64)+1 {
        if n % i == 0 {
            result = i;
            break;
        }
    }

    if result == n {
        return vec![n];
    } else {
        let mut v1 = vec![result];
        let mut v2 = trivial_division(n / result);

        v1.append(&mut v2);

        return v1;
    }
}

fn main() {
    println!("{:?}", trivial_division(238528));
}

1. 素因数が2である確率は3である確率より大きいですよね？ 範囲aからb（$a, b \in \mathbb{Z}$）の中に、素因数が$x$の数は大体$(b-a)/x$くらいあるので、一般的に$x < y$なら素因数が$x$である確率は$y$である確率より大きいのです。なので、小さい方から探したほうが効率が良いのです。 ↩

2. $N$の素因数は$\sqrt{N}$を超えることもありますが、最小の素因数は$\sqrt{N}$以下です。なぜなら、$\sqrt{N}$より大きい素因数$p$が存在すれば$N$が合成数であることから他の因数$\mathrm{f} = N / p$が存在するはずで、これは$\sqrt{N}$以下であるからです。 ↩

3. $N$は合成数って言って話進めてますので、は$2 \le p \le \lfloor \sqrt{N} \rfloor $で割り切れない場合は上の話では存在しません。（だから、ん？？？ってなった人に向けてこの注釈を書いてます）実際のアルゴリズムでは$N$は自然数なので、その範囲になかった場合は素数だということです。なんかうまい書き方が見つからなかったorz ↩