C 프로그래밍 | 최소 공배수 (LCM) 계산 | 재귀

소개

이 랩에서는 재귀 (recursion) 를 사용하여 두 숫자의 LCM (최소 공배수, Least Common Multiple) 을 구하는 C 프로그램을 작성합니다. LCM 은 두 숫 모두로 나누어 떨어지고 나머지가 없는 가장 작은 양의 정수입니다.

LCM 개념 이해

프로그래밍을 시작하기 전에 LCM 의 개념을 이해해 봅시다. 두 정수의 LCM 은 두 숫자 모두의 배수인 가장 작은 양의 정수입니다. 두 숫자의 LCM 을 찾기 위해 다음 공식을 사용할 수 있습니다.

LCM = (number1 * number2) / GCD

여기서 number1과 number2는 LCM 을 구해야 하는 두 숫자이고, GCD 는 두 숫자의 최대 공약수 (Greatest Common Divisor) 입니다.

새 C 파일 생성

프로그램을 작성할 ~/project/ 디렉토리에 main.c라는 새 C 파일을 생성해 보겠습니다.

코드 작성

다음 코드를 복사하여 main.c 파일에 붙여넣으세요.

#include<stdio.h>

int find_lcm(int, int); // function prototype declaration

int main()
{
    int a, b, lcm;
    printf("Enter two integers to find LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // function call
    printf("LCM of %d and %d is %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // function definition
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

프로그램 컴파일 및 실행

main.c 파일을 저장하고 터미널에서 다음 명령을 사용하여 프로그램을 컴파일합니다.

gcc main.c -o main

다음 명령을 사용하여 프로그램을 실행합니다.

./main

프롬프트가 표시되면 두 개의 정수를 입력하면 프로그램이 두 숫자의 LCM(최소 공배수) 을 표시합니다.

코드 이해

방금 작성한 코드를 이해해 봅시다.

먼저 #include<stdio.h>를 사용하여 표준 입출력 라이브러리를 프로그램에 포함시킵니다.
프로그램의 뒷부분에서 정의할 find_lcm 함수 프로토타입을 선언합니다. 이는 find_lcm 함수를 실제 정의 전에 main 함수에서 호출하기 때문에 필요합니다.
main 함수에서 세 개의 정수 변수 a, b, lcm을 선언합니다.
printf를 사용하여 사용자에게 두 개의 정수를 입력하라는 메시지를 표시하고 scanf를 사용하여 입력을 받습니다.
그런 다음 find_lcm 함수를 호출하고 a와 b를 인수로 전달합니다.
find_lcm 함수는 두 개의 정수 인자 a와 b를 받아 재귀 (recursion) 를 사용하여 두 숫자의 LCM(최소 공배수) 을 반환합니다.
현재 배수를 확인하는 값인 temp 변수를 1 로 초기화합니다. 이 변수는 static 으로 선언됩니다.
각 재귀에서 temp가 a와 b의 배수인지 확인합니다.
배수인 경우 temp를 LCM 으로 반환합니다.
배수가 아닌 경우 temp를 증가시키고 LCM 을 찾을 때까지 find_lcm 함수를 재귀적으로 호출합니다.

프로그램 테스트

다양한 입력 값으로 프로그램을 테스트하고 올바른 LCM(최소 공배수) 출력을 생성하는지 확인합니다.

전체 코드

다음은 재귀를 사용하여 두 숫자의 LCM(최소 공배수) 을 구하는 C 프로그램의 전체 코드입니다.

#include<stdio.h>

int find_lcm(int, int); // 함수 프로토타입 선언

int main()
{
    int a, b, lcm;
    printf("LCM 을 찾기 위해 두 정수를 입력하세요:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // 함수 호출
    printf("%d와 %d의 LCM 은 %d입니다.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // 함수 정의
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

요약

이 랩에서는 재귀를 사용하여 두 숫자의 LCM(최소 공배수) 을 구하는 C 프로그램을 작성하는 방법을 배웠습니다. 재귀 함수를 사용하여 LCM 을 구하고 프로그램의 각 단계를 자세히 설명했습니다. 또한 터미널을 사용하여 C 프로그램을 컴파일하고 실행하는 방법도 배웠습니다.

C 언어 재귀를 이용한 LCM 계산

소개