C 言語プログラミングにおける最大公約数の求め方

はじめに

C 言語のプログラミングでは、最大公約数（GCD: Greatest Common Divisor）を求める処理が頻繁に行われます。最大公約数を求める方法としては、2 通りの方法が一般的に使われています。1 つは、ユークリッドの互除法を用いて、繰り返し引き算を行うことで最大公約数を求める方法です。このハンズオンでは、これら 2 つの方法をそれぞれ説明します。

Skills Graph

ユークリッドの互除法を使う

ユークリッドの互除法は、除数を割り算の余りに置き換えることで最大公約数を求めるアルゴリズムです。余りが 0 になったとき、最大公約数はその除数になります。

1.1 整数型の変数 a と b を宣言して、解を始めます。

    int a, b;

1.2 次に、ユーザーに a と b の値を入力してもらいます。

    printf("Enter two numbers: \n");
    scanf("%d %d", &a, &b);

1.3 その後、a を b で割った余りが 0 になるまで実行する while ループを作成します。

    while(a!=b)
    {
        if(a>b)
            a=a-b;
        else
            b=b-a;
    }

1.4 最後に、2 つの数の最大公約数を表示します。

    printf("The GCD of two numbers is %d", a);

繰り返し引き算の方法を使う

この方法では、大きい方の値から小さい方の値を繰り返し引き算していき、両方の値が等しくなるまで行います。そのときの値が最大公約数になります。

2.1 整数型の変数 num を宣言し、0 で初期化します。

    int num = 0;

2.2 整数型の変数 x を宣言し、2 で初期化します。

    int x = 2;

2.3 最大公約数を求める整数の数をユーザーに入力してもらいます。

    printf("Enter the number of integers you want to find the GCD of: ");
    scanf("%d", &num);

2.4 次に、ユーザーに数値を入力してもらいます。

    printf("Enter %d numbers:\n", num);
    int arr[num];
    for(int i = 0; i < num; i++)
    {
        scanf("%d", &arr[i]);
    }

2.5 ここでは、入力値を使って繰り返し引き算の方法を用いて最大公約数を計算します。入力値の最大公約数を計算するために、gcd() 関数を呼び出します。

    int result = arr[0];
    for(int i = 1; i < num; i++)
    {
        result = gcd(result, arr[i]);
    }

方法の組み合わせ

このステップでは、方法を組み合わせて実装を完了します。

3.1 繰り返し引き算の方法で最大公約数を求める際に使用する gcd() 関数を宣言します。

    int gcd(int a, int b)
    {
        if(b==0)
            return a;
        else if(a >= b && b > 0)
            return gcd(b,a%b);
        else
            return gcd(b,a);
    }

3.2 新しい変数 gcd_result を宣言し、0 で初期化します。

    int gcd_result = 0;

3.3 ユーザーに数値を入力してもらい、入力値が 0 であることが検出されるまで新しいループを作成します。

    printf("Enter numbers. To exit enter 0\n");
    while(1)    // 入力を受け取る無限ループ
    {
        int num;
        scanf("%d", &num);
        if(num < 1)
            break;
        else if(gcd_result == 0)
            gcd_result = num;
        else if(num < gcd_result)
            gcd_result = gcd(num, gcd_result);
        else
            gcd_result = gcd(gcd_result, num);
    }

3.4 最後に、printf 関数を使って最終結果を表示します。

    printf("The GCD of all the entered numbers is: %d\n", gcd_result);

まとめ

この実験では、C 言語のプログラミングにおいて整数のグループの最大公約数（GCD）を計算する 2 つの方法：ユークリッドの互除法と繰り返し引き算の方法を学びました。これらの方法をどのように使用するかを詳細な説明とサンプルコードブロックで示しました。さらなる理解のために、main.c ファイルのコードを修正して実行することをお勧めします。