C LANGUAGE TECHNOLOGY

【C言語】ユークリッドの互除法で最大公約数と最小公倍数の計算

悩んでいる人

C言語で最大公約数と最小公倍数の計算方法を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

ユークリッドの互除法

ユークリッドの互除法とは,2つの自然数の最大公約数を計算するアルゴリズムです.

2つの自然数a,b(a≧b)について,aをbで割った余りをrとすると,aとbとの最大公約数はbとrとの最大公約数に等しいです.

なので,bをr(b>r)で割った余りr',r'とrの大きい方から小さい方で割った余りr'',と繰り返し実行し,余りが0になった時の割る数がaとbの最大公約数になります.

ユークリッドの互除法は,紀元前300年頃に記されたユークリッドによる明示的に記述された最古のアルゴリズムとして知られています.

2つの自然数aとbの最小公倍数(LCM:Least Common Multiple)の計算は,最大公約数(GCD:Greatest Common Divisor)を利用すると下式になります.

$$LCM = \frac{a * b}{GCD}$$

最小公倍数は最大公約数がわかると簡単に計算できます.

C言語のユークリッドの互除法で最大公約数と最小公倍数の計算

C言語のユークリッドの互除法で最大公約数と最小公倍数の計算コードは以下になります.

実行結果は以下になります.

3行目の行末に6と4を入力し,これらの最大公約数が2,最小公倍数が12と正しく計算できていることがわかります.

拡張ユークリッドの互除法

自然数a,bの最大公約数をgcd(a,b)と表す時,拡張ユークリッドの互除法を利用して, \(ax + by = gcd(a, b)\) の解となる整数x,yの組を見つけることができます.

例えば,6,4の最大公約数を考えてみましょう.

これらの最大公約数は2になります.

$$6x + 4y = 2$$

拡張ユークリッドの互除法でxとyを計算すると,x = 1,y = -1になります.

上式にxとyを代入すると下式になり,正しいことがわかります.

$$6 * 1 + 4 * -1 = 2$$

拡張ユークリッドの互除法で最大公約数と整数解の計算

拡張ユークリッドの互除法で最大公約数と整数解の計算コードは以下になります.

実行結果は以下になります.

a,b,x,yが正しく計算できていることがわかります.

まとめ

C言語のユークリッドの互除法で最大公約数と最小公倍数の計算方法を紹介しました.

ユークリッドの互除法でアルゴリズムの基本を習得しましょう!

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール4社で自分に合うスクールを見つけましょう.

-C LANGUAGE, TECHNOLOGY
-, , , , , ,