C LANGUAGE TECHNOLOGY

【C言語】素因数分解アルゴリズム【試し割り法,SPF法】

悩んでいる人

C言語で素因数分解アルゴリズムを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

本記事は,素数の判定方法を理解していることを前提とします.

C言語 素数
【C言語】エラトステネスの篩(ふるい)で素数の判定【サンダラムの篩,アトキンの篩】

こういった悩みにお答えします. こういった私から学べます. 目次1 エラトステネスの篩(ふるい)2 サンダラムの篩3 アトキンの篩4 まとめ エラトステネスの篩(ふるい) エラトステネスの篩(ふるい) ...

続きを見る

素因数分解

素因数分解とは,ある正の整数(自然数)を素数の積の形で表すことです.

例えば,12を素因数分解した場合,\(12 = 2^2*3\)になります.

本記事では,C言語で以下の素因数分解アルゴリズムを紹介していきます.

  • 試し割り法
  • SPF法

試し割り法

試し割り法は,素因数分解する整数nを小さい順に割ってみて,割り切れるかどうかを調べるアルゴリズムです.

試し割り法は,シンプルでとても理解しやすい素因数分解アルゴリズムです.

試し割り法の計算量は,\(\mathcal{O}(\sqrt{n})\)になります.

計算量は指数関数的に増加しますが,現在の高速な素因数分解アルゴリズムでも同様に指数関数的に増加します.

なので,試し割り法は実用的なアルゴリズムと言えるでしょう.

試し割り法のコードは以下になります.

実行結果は以下になります.

Smallest Prime Factor(SPF)法

Smallest Prime Factor(SPF)法は,エラトステネスの篩を利用して1からnまでの数に対する最小の素因数を前処理で求めてから素因数分解するアルゴリズムです.

前処理で求めたSPFを利用することで,素因数分解する本処理の計算量を減らすことができます.

具体的には,SPF法の前処理の計算量は\(\mathcal{O}(n \log\log n)\),本処理の計算量は\(\mathcal{O}(\log n)\)になります.

計算量のlogの底は2なので,n = 4の場合,試し割り法とSPF法の本処理の計算量は等しくなります(\(\sqrt{4} = \log_2 4 = 2\)).

\(\sqrt{n}\)と\(\log n\)はどちらも単調増加ですが,nが大きくなるほど\(\sqrt{n} - \log n\)は大きくなります.

しかし,SPF法の前処理の計算量\(\mathcal{O}(n \log\log n)\)が影響するので,1個の整数を素因数分解する場合,試し割り法はSPF法より速いです.

複数の整数を素因数分解する場合,SPF法は試し割り法より高速化できます.

なぜかというと前処理は1回,本処理は複数回あるからですね.

興味があるあなたは以下の記事を読みましょう!(C++のコードです.)

SPF法を利用するコードは以下になります.

実行結果は以下になります.

素因数分解とサマーウォーズ

素因数分解とアニメ映画「サマーウォーズ」は密接な関係があります.

サマーウォーズのネタになったRSA暗号が解けるかどうか検証している動画です.

面白いので,是非観ましょう!

まとめ

C言語で素因数分解アルゴリズムを紹介しました.

具体的には,試し割り法,SPF法を解説しました.

また,素因数分解とサマーウォーズの関係がわかりました.

素因数分解の高速化手法として,主に以下の方法があります.

興味があるあなたは,是非実装してみましょう!

素因数分解の高速化の現状について語る記事ですので,是非読みましょう!

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , ,