数学

今回は素因数分解アルゴリズムかつ決定的素数判定アルゴリズムの「試し割り法」について解説していきます。試し割り法は素因数分解をするためのアルゴリズムですが、素因数分解をすればその数が素数であるかも同時に判定することができるため素数判定ア ...

今回は決定的素数判定アルゴリズムの「エラトステネスの篩ふるい」について解説していきます。
素数判定アルゴリズムは数多く存在しますがその中でも非常に単純で理解しやすいアルゴリズムです。

それもそのはず、このアルゴリズ ...

今回は確率的素数判定アルゴリズムの「フェルマーテスト」について解説していきます。
フェルマーというと『フェルマーの最終定理』で聞いたことがあるという人も多いのではないでしょうか。最終定理という名前で有名なこの定理ですが別名『フ ...

今回は任意の自然数の最大公約数を求める「ユークリッドの互除法」について解説していきます。
アルゴリズムとしての歴史は非常に深く、明示的に記述された最古のアルゴリズムといわれていてその誕生は紀元前3世紀にまで遡るアルゴリズムです ...

今回は乱択アルゴリズム「モンテカルロ法」について解説していきます。
このモンテカルロ法、あえて処理の中で乱数を使ってランダム性を出すというアルゴリズムなのですが、ランダム性を出しているのにも関わらず最終的にはある1つの答えが浮 ...

今回は凸包とつほうアルゴリズムの「ギフト包装法」について解説していきます。
凸包アルゴリズムはいろいろな種類がありますが、ギフト包装法は最も単純で理解しやすいアルゴリズムです。その分、他の凸包アルゴリズムに比べて処理時間は多く ...