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

Aug 19 2018

試し割り法は素因数分解の一番愚直なアルゴリズムです。この解説をします。

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

この解説をします。

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

† 素因数が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

Read more?

数学 I(三角法) を勉強していく上で思ったこととかメモ

Oct 11 2018

黄茶の旅日記の様なものです。数Iの三角法です。

画面指紋認証の仕組みって

Jun 11 2018

最近、画面指紋認証の記事を見かけまして、「そういやこれどうやって出来てるのかな...」と思って記事探してみてもなかったので(英語でも少なかった)、幾つかのページ(参考文献)から引っ張り出してきた情報を元に記事を書きます

Rustにおけるファイル分割

Rustは、モジュールシステムも色々決まりがあって整っているので、単にファイルを分けて書こうと思った場合にも、整った綺麗な書き方をするには難しい言語に感じます。自分も、丁度Rustでプログラムを書いていた時に迷って良いリポジトリから良い書き方を見つけたのでその紹介をしようと思います

Jul 19 2018

042933964230の暗号について調べてみた

Apr 23 2018

謎のサイトと言われて少し前に話題になったやつを調べてみました

日本一早いサイト選手権

阿部寛のホームページが爆速なのでそれよりはやいページ無いかなぁと適当に探してみた結果です。

Sep 22 2018

[円柱の体積文字列] 英単語をgrepできるサイトを作りました

Sep 17 2018

円の体積文字列で別の例を探すために英単語をgrep出来るサイトを作りました

数学 I(二次関数) を勉強していく上で思ったこととかメモ

黄茶の二次関数が終わったので、その学習中に思ったことを適当にメモしておきます

Sep 16 2018

IEは最高のブラウザ / IE is the best browser

Sep 16 2018

世間では何故かIEが蔑まれているようですが、そんなブラウザにも素晴らしいところが沢山あるのです

Explain Backpropagation Like I'm Five

Jul 13 2018

Recently, there are many successful news with the artificial intelligence (AI). Machine translation, object detection, automatic modeling, motion capture and so on... Even the optical illusion that only your brain should be able to perform has been achieved by the AI.

線の長さを積分で考えてみる

Sep 11 2018

今回は、前回積分を使って面積(小さな面積の集合)を求めたので、今回は線(小さな線の集合)の長さを求めていければ良いなぁみたいな感じでやっていけたらと思っています。

積分で原始関数の差を求めると元の函数の面積が出る理由

今回は積分の面白い性質である、原始関数の差が元の函数の面積となるという性質についてそうなる理由を気持ちだけでも書いていきます。

Sep 04 2018

「国語に関する世論調査」を読んで思ったこととか

Aug 28 2018

国の日本語に関する調査を見て最近の日本語の変化について知りました。

新しいブログシステムを構築したのでやったことを記録

前の古臭いブログシステムのままだと嫌だったので、新しいブログシステムを構築しました。

Aug 22 2018

共用サーバーで非同期通信チャットアプリを作る

今日は、さくらサーバーのライトプランという制限が多いサーバーでなんとか非同期通信を実現すべく奮闘したので、その記録をしたいと思います。

Aug 21 2018

前にブログに追加した機能

前にブログに追加した機能が使えるかどうかのテスト用.

Aug 21 2018