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

Method

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));
}

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

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

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