NAL-6295 https://blog.hatena.ne.jp/NAL-6295/ NAL-6295の舌先三寸 https://nal-6295.hatenadiary.org/ 算数 2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 素因数分解しなくても、ユークリッドの互除法という方法を使えば、もっと早く算出できるという事がわかった。 というか、読んだから分かったんだけど。20と12なら 20/12 = 1あまり8 12 / 8 = 1 あまり 4… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnal-6295.hatenadiary.org%2Fentry%2F20080711%2Fp3" title="最大公約数を算出するためのユークリッドの互除法 - NAL-6295の舌先三寸" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-07-11 00:00:00 rich https://nal-6295.hatenadiary.org/entry/20080711/p3 1.0 100%