或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

アルゴリズム

Rubyで素数判定の繰り返しを効率化してみた話

はじめに とあるプログラミング問題に取り組んでる時、連続する数をそれぞれ素数か否かの判断を結構な回数繰り返す処理をRubyで書いていたのですが、もう少し処理速度が上がらんかなーと試行錯誤した結果、処理が効率化できたー。というお話です。 問題 実際…

最大公約数、最小公倍数の求め方/ユーグリットの互除法

今回もアルゴリズムに関して学んだ知識のメモ。ユーグリットの互除法について調べてみました。 ユーグリットの互除法とは 最大公約数を求める手法です。 ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大…

エラトステネスのふるいを実装してみる

アルゴリズムに関する知識も自分の中にストックしておきたいということで、今回は「エラトステネスのふるい」について調査したものをメモ。 エラトステネスのふるいとは 素数の一覧を簡易的に求める手法です。 エラトステネスの篩 (エラトステネスのふるい、…

組み合わせの数を計算する

プログラミングの問題を解いてると、組み合わせの数を計算する必要が出てきたので、調査した内容をメモ。 組み合わせの数とは 高校数学なんかで習った記憶は微かにあるが、大分忘れてるので勉強しなおし。 こちらのサイトの説明が非常に丁寧でした。組み合わ…