最大公約数

数ヶ月まえ 子供から 最大公約数について 質問があった。

 

 

で

 

 

素因数分解じゃ！！！

 

まだ、素数を習ってないらしいｗｗｗｗ

 

まぁ でも 知ってるはず！！
前に俺が教えたから！！！ ｗｗｗ　　数の不思議は楽しいな～ ＾＾

 

それから 数ヶ月。。。

夏休みの宿題で おもいっきり 間違えているし ｈｈｈｈｈｈ

もう一度、一から解説orz

今回は 本当に理屈？ を分かったとの こと。。。。本当か？？ｗ

 

結論から いうと 素因数分解して

 

・共通部を 取り出したのが 最大公約数。
・全てを含めたのが 最小公倍数。

 

なぜ そうなるのか。。。 文章にするのが面倒なので省略！

 

 

でも、これって プログラムで最大公約数を求める時には使わないんだよね～
素因数分解が めっちゃ面倒なんです。

 

人間だと 感覚で この数は ２で割れるな 。。次は３。。 ５。。 ７。。と
適当な素数を選ぶけど、パソコンはそんなに賢くない！！！！

で 使われるのが 「ユークリッドの互除法」
プログラムを勉強する時の もっともメジャー？ な アルゴリズムの１つ。

これを 数式で証明したのを 見た事あるけど。。。俺のしょぼい 頭では 理解不能ｗｗｗ

しかし 今回、しっかり理解したくて 悪戦苦闘してみたｗ

 

 

で

 

図で 考えると無茶苦茶、簡単な事を知ったｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

２つの数字 ａ と ｂ の 最大公約数 って ようは 縦の長さａ 横の長さ ｂ の敷地に １辺ｃの正方形を敷き詰める時 もっとも大きい 正方形のｃ は 何？ って ことだから 外から 敷地を 切り刻んで いけば ＯＫ なんだよな。
最後に出来た 正方形がの １辺ｃ が 最大公約数になる。

 

説明 下手だけど 自分で 考えると めっちゃ おもろいよ。。。

 

VBAで コードを 書くと こんな感じ

 

「ユークリッドの互除法」を 利用して 最大公約数を求める コードに起こす時、元の公式の影響で 割り算を使いがちなんだけど 下記のように 大きい数字から 小さい数字を引くだけでＯＫなんだなｗｗｗ
本質を理解すると よりコンパクトな コードを起こせる。