再帰を使った素数または合成数

はじめに

この実験では、再帰を使って数が素数か合成数かをチェックする C プログラムを書く方法を学びます。素数とは、1 とそれ自身のみで割り切れる数であり、合成数とは素数でない数です。再帰を使ってプログラムを書きます。再帰とは、問題をより小さく、より単純な問題に分解することで問題を解決する手法です。

Skills Graph

ユーザー入力の取得

まず、scanf 関数を使ってユーザーに正の整数を入力してもらい、その数が素数か合成数かをチェックします。int main() 関数内の main.c ファイルに次のコードを追加します。

#include <stdio.h>

int main()
{
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return 0;
}

数をチェックする再帰関数の作成

このステップでは、数が素数か合成数かをチェックする再帰関数を作成します。この関数は 2 つの引数を取ります。チェックする数と、2 で割った数から始まるカウンタ変数です。カウンタが 1 に達した場合、関数は 1 を返して数が素数であることを示します。それ以外の場合、関数は減少したカウンタ変数を使って自身に再帰呼び出しを行います。いずれかの時点で、数がカウンタ変数で割り切れて余りがない場合、関数は 0 を返して数が合成数であることを示します。main.c ファイルの末尾に次のコードを追加します。

int isPrime(int n, int c)
{
    if (c == 1) {
        return 1;
    } else {
        if (n % c == 0) {
            return 0;
        } else {
            return isPrime(n, c - 1);
        }
    }
}

結果のチェックと出力

このステップでは、数が素数か合成数かをチェックするために isPrime 関数を呼び出します。関数の結果に基づいて、適切なメッセージをユーザーに出力します。プログラムを完成させるために、main.c ファイルの末尾に次のコードを追加します。

int main()
{
    int num, prime;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    prime = isPrime(num, num/2);
    if (prime == 1) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is a composite number.\n", num);
    }
    return 0;
}

プログラムのビルドと実行

このステップでは、プログラムをコンパイルして実行します。ターミナルを開き、main.c ファイルがあるディレクトリに移動します。ターミナルに次のコマンドを追加してプログラムをコンパイルします。

gcc main.c -o main

プログラムを実行するには、次のコマンドを追加します。

./main

プロンプトが表示されたら正の整数を入力し、Enter キーを押します。プログラムはその数が素数か合成数かを出力します。

まとめ

この実験では、再帰を使って数が素数か合成数かをチェックする C プログラムを書く方法を学びました。また、scanf 関数を使ってユーザー入力を取得し、再帰関数を使って数が素数か合成数かをチェックし、結果をユーザーに出力する方法も学びました。再帰は、問題を小さく単純な問題に分解することが必要な問題を解くための便利な手法です。