数ヶ月まえ 子供から 最大公約数について 質問があった。
で
素因数分解じゃ!!!
まだ、素数を習ってないらしいwwww
まぁ でも 知ってるはず!!
前に俺が教えたから!!! www 数の不思議は楽しいな~ ^^
それから 数ヶ月。。。
夏休みの宿題で おもいっきり 間違えているし hhhhhh
もう一度、一から解説orz
今回は 本当に理屈? を分かったとの こと。。。。本当か??w
結論から いうと 素因数分解して
・共通部を 取り出したのが 最大公約数。
・全てを含めたのが 最小公倍数。
なぜ そうなるのか。。。 文章にするのが面倒なので省略!
でも、これって プログラムで最大公約数を求める時には使わないんだよね~
素因数分解が めっちゃ面倒なんです。
人間だと 感覚で この数は 2で割れるな 。。次は3。。 5。。 7。。と
適当な素数を選ぶけど、パソコンはそんなに賢くない!!!!
で 使われるのが 「ユークリッドの互除法」
プログラムを勉強する時の もっともメジャー? な アルゴリズムの1つ。
これを 数式で証明したのを 見た事あるけど。。。俺のしょぼい 頭では 理解不能www
しかし 今回、しっかり理解したくて 悪戦苦闘してみたw
で
図で 考えると無茶苦茶、簡単な事を知ったwwwwwwwwwwwwwwwwww
2つの数字 a と b の 最大公約数 って ようは 縦の長さa 横の長さ b の敷地に 1辺cの正方形を敷き詰める時 もっとも大きい 正方形のc は 何? って ことだから 外から 敷地を 切り刻んで いけば OK なんだよな。
最後に出来た 正方形がの 1辺c が 最大公約数になる。
説明 下手だけど 自分で 考えると めっちゃ おもろいよ。。。
VBAで コードを 書くと こんな感じ
「ユークリッドの互除法」を 利用して 最大公約数を求める コードに起こす時、元の公式の影響で 割り算を使いがちなんだけど 下記のように 大きい数字から 小さい数字を引くだけでOKなんだなwww
本質を理解すると よりコンパクトな コードを起こせる。