互除法の利用
最大公約数を求めるとき、素因数分解をすれば求められます。
ただ、37や61などの大きい素数の場合、見つけるのは困難です。
そこで役立つのがユークリッドの互除法です。
単に互除法と言ったりもします。
「ある2つの自然数a、bがあり、aをbで割った商をp、余りをrとしたとき、aとbの最大公約数はbとrの最大公約数に等しい」
この性質を利用することにより、より小さな数で最大公約数を探すことができます。
文字を含む場合にも有効ですよ。
ここから先は
0字
/
1画像
¥ 100
この記事が気に入ったらサポートをしてみませんか?