今日の人気記事

  1. サンプルプログラム集
  2. 配列に格納した数値を昇順ソート
  3. 変数の値を出力 - printf 関数
  4. MinGW - gcc のインストール - Windows環境
  5. 10進数を2進数に変換

入力した2つの自然数の最大公約数を求める

スポンサーリンク

入力した n個の整数から一番大きい数値を探すサンプルプログラムを紹介します。

ここでは「ユークリッドの互除法」を用いて、最大公約数を求めます。

ユークリッドの互除法

ユークリッドの互除法は、2つの自然数から最大公約数を求める手法のことです。

大きい自然数 a を小さい自然数 b で割った余りを r とすると、a と b の最大公約数は b と r の最大公約数に等しくなります。

プログラムでは次のようなアルゴリズムになります。

  1. 2つの自然数を入力
  2. a % b = r を計算
  3. b % r を計算
  4. 2. と 3. を r = 0 になるまで繰り返す
  5. b が最大公約数
スポンサーリンク

サンプルプログラム

それではサンプルプログラムをみてみましょう。

/*
 * C言語のサンプルプログラム - Webkaru
 * - 入力した2つの自然数の最大公約数を求める -
 */
#include <stdio.h>

int main(void)
{

  int a, b, r, tmp;

  printf("2つの自然数を入力してください。\n");
  printf("1つ目の自然数 = ");
  scanf("%d", &a);
  printf("2つ目の自然数 = ");
  scanf("%d", &b);

  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

  /* 最大公約数を出力 */
  printf("最大公約数 = %d\n", b);

  return 0;
}

サンプルプログラムで使っている構文

実行結果

いくつかの実行結果です。

1つ目の自然数 = 3
2つ目の自然数 = 6
最大公約数 = 3
2つの自然数を入力してください。
1つ目の自然数 = 12
2つ目の自然数 = 4
最大公約数 = 4
2つの自然数を入力してください。
1つ目の自然数 = 72   
2つ目の自然数 = 48
最大公約数 = 24

このように入力した n個の整数の中から一番大きい数を探して、出力します。

スポンサーリンク

関連記事(一部広告含む)