プログラミングで最大公約数と最小公倍数を求めるプログラムに挑戦

2022年3月15日

Javascript テクノロジー

eyecatch プログラミングはゲーム感覚の、ユゲタです。 最近SNSでよく見かける、入社試験で行った問題で、「2つの数値から最大公約数を返すプログラミングをせよ」というのを見かけて、自分でもやってみたくなったので、ブログで挑戦してみたいと思います。 ちなみに、最大公約数を求めるので、最小公倍数も求めてみたいと思います。 なんとなく、この2つは、関連する処理になりそうな気がするという想定なんですよね。

最大公約数?最小公倍数?

中学校の数学で習った事を覚えていますが、ようするに、 最大公約数というのは、2つの数値で割り切れる(割った後整数になる値)一番大きい数値で、 最小公倍数は、2つの値に整数値を掛け合わせていった時に、同じ数になる一番小さい値の事です。 忘れてしまっている人は、思い出してみましょう!

最大公約数を求めるプログラム

function GreatestCommonDivisor(a , b){ for(let i=a-1; i>=0; i--){ var a2 = a/i var b2 = b/i if(~~a2 === a2 && ~~b2 === b2){ console.log(i) break } } } var a = Math.floor(Math.random() * 99)+1 var b = Math.floor(Math.random() * 99)+1 console.log(a +" & "+ b) GreatestCommonDivisor(a , b) > 56 & 42 > 14 できた! ランダムで100までの数値を2つ出してその2つの数値の最大公約数を求めています。 1ずつ引き算をしていって、それぞれが同時に小数点がなくなった状態が最大公約数と判定しています。 もっと短くかけそうだけど、わかりやすいこの状態でゴールにしましょう。

最小公倍数を求めるプログラム

function LatestCommonMultiple(a , b){ // 掛け合わせた最大値を求める var maxMultiple = a * b // 大きい方の数値を取得 var largeNum = a > b ? a : b // for(i=largeNum+1; i<=maxMultiple; i++){ var a2 = i / a var b2 = i / b if(a2 === ~~a2 && b2 === ~~b2){ console.log(i) return i } } return null } var a = Math.floor(Math.random() * 99)+1 var b = Math.floor(Math.random() * 99)+1 console.log(a +" & "+ b) LatestCommonMultiple(a , b) > 95 & 12 > 1140 やはり想像通り、最大公約数と似たような感じで作成できました。 今回は、2つの値を掛け合わせて、その数字を上限として、加減をa,bのどちらか大きい値で、1つずつ値を足して行きます。 そして、2つの値とも、足し込んだ数値を割った時に、整数になれば、その値が最大公約数になるという事です。 こういうアルゴリズム的なプログラミングは一度は書いておくと、その後スキルが上がった時に、めちゃくちゃ効率が良くなった事が自分で判定できるようになるので、オススメです。

人気の投稿

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。

ブログ アーカイブ