재귀를 사용한 소수 또는 합성수 판별

소개

이 랩에서는 재귀를 사용하여 숫자가 소수 (prime number) 인지 합성수 (composite number) 인지 확인하는 C 프로그램을 작성하는 방법을 배웁니다. 소수는 1 과 자기 자신으로만 나누어 떨어지는 숫자이며, 합성수는 소수가 아닌 숫자입니다. 우리는 재귀 (recursion) 를 사용하여 프로그램을 작성할 것입니다. 재귀는 문제를 더 작고 간단한 문제로 분해하여 해결하는 기술입니다.

사용자 입력 받기

먼저, scanf 함수를 사용하여 소수인지 합성수인지 확인할 양의 정수를 입력하도록 사용자에게 요청합니다. int main() 함수 내의 main.c 파일에 다음 코드를 추가합니다.

#include <stdio.h>

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

숫자 확인을 위한 재귀 함수 작성

이 단계에서는 숫자가 소수인지 합성수인지 확인하는 재귀 함수를 작성합니다. 이 함수는 두 개의 인수를 받습니다. 확인하려는 숫자와 숫자를 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 키를 누릅니다. 프로그램은 숫자가 소수인지 합성수인지 출력합니다.

요약

이 랩에서는 재귀를 사용하여 숫자가 소수 (prime number) 인지 합성수 (composite number) 인지 확인하는 C 프로그램을 작성하는 방법을 배웠습니다. 또한 scanf 함수를 사용하여 사용자 입력을 받고, 숫자가 소수인지 합성수인지 확인하는 재귀 함수를 작성하고, 결과를 사용자에게 출력하는 방법을 배웠습니다. 재귀는 문제를 더 작고 간단한 문제로 분해하는 문제를 해결하는 데 유용한 기술입니다.