C 언어로 최소 공배수 (LCM) 계산 방법

소개

이 실습에서는 C 프로그래밍을 사용하여 두 정수의 최소 공배수 (LCM) 를 찾는 방법을 배웁니다. 이 실습은 사용자 입력으로 두 정수를 읽는 것부터 시작하여, LCM = (a*b)/GCD(a,b) 공식을 사용하여 LCM 을 계산하고, 마지막으로 결과를 출력하는 단계별 과정을 다룹니다. 이 실습을 마치면 유클리드 알고리즘과 같은 수론 개념을 적용하여 C 에서 실제 문제를 해결하는 방법에 대한 확실한 이해를 얻게 될 것입니다.

두 정수 읽기

이 단계에서는 최소 공배수 (LCM) 를 계산하는 첫 번째 단계로, C 프로그래밍에서 사용자 입력으로 두 정수를 읽는 방법을 배웁니다.

먼저 LCM 프로그램을 위한 새로운 C 파일을 생성합니다.

cd ~/project
nano lcm.c

이제 두 정수를 읽는 다음 코드를 추가합니다.

#include <stdio.h>

int main() {
    int a, b;

    printf("두 개의 양의 정수를 입력하세요:\n");
    printf("첫 번째 숫자: ");
    scanf("%d", &a);

    printf("두 번째 숫자: ");
    scanf("%d", &b);

    printf("입력한 숫자: %d 와 %d\n", a, b);

    return 0;
}

프로그램을 컴파일하고 실행합니다.

gcc lcm.c -o lcm
./lcm

예시 출력:

두 개의 양의 정수를 입력하세요:
첫 번째 숫자: 12
두 번째 숫자: 18
입력한 숫자: 12 와 18

코드를 자세히 살펴보겠습니다.

scanf() 함수는 사용자로부터 정수 입력을 읽는 데 사용됩니다.
%d 형식 지정자는 정수 입력을 위해 사용됩니다.
&a와 &b는 입력 값이 저장될 메모리 주소를 전달합니다.

LCM = (a*b)/GCD(a,b) 사용

이 단계에서는 최소 공배수 (LCM) 를 LCM(a,b) = (a*b)/GCD(a,b) 공식을 사용하여 계산합니다. 먼저 유클리드 알고리즘을 사용하여 최대 공약수 (GCD) 를 계산하는 함수를 만들겠습니다.

lcm.c 파일을 다음 코드로 업데이트합니다.

#include <stdio.h>

// 유클리드 알고리즘을 사용하여 GCD 를 계산하는 함수
int calculateGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// LCM 을 계산하는 함수
int calculateLCM(int a, int b) {
    return (a * b) / calculateGCD(a, b);
}

int main() {
    int a, b, lcm;

    printf("두 개의 양의 정수를 입력하세요:\n");
    printf("첫 번째 숫자: ");
    scanf("%d", &a);

    printf("두 번째 숫자: ");
    scanf("%d", &b);

    lcm = calculateLCM(a, b);

    printf("%d 와 %d 의 최소 공배수는: %d\n", a, b, lcm);

    return 0;
}

프로그램을 컴파일하고 실행합니다.

gcc lcm.c -o lcm
./lcm

예시 출력:

두 개의 양의 정수를 입력하세요:
첫 번째 숫자: 12
두 번째 숫자: 18
12 와 18 의 최소 공배수는: 36

핵심 구성 요소를 살펴보겠습니다.

calculateGCD()는 유클리드 알고리즘을 구현하여 최대 공약수를 찾습니다.
calculateLCM()은 공식 LCM(a,b) = (a*b)/GCD(a,b) 를 사용합니다.
유클리드 알고리즘은 나머지를 반복적으로 계산하여 효율적으로 GCD 를 찾습니다.

LCM 출력

이 마지막 단계에서는 다양한 입력 조합에 대한 LCM 프로그램의 출력을 확인합니다. 다양한 정수 쌍으로 프로그램을 테스트하여 LCM 계산을 보여줍니다.

(아직 컴파일하지 않았다면) 프로그램을 컴파일합니다.

cd ~/project
gcc lcm.c -o lcm

다른 입력 조합으로 프로그램을 실행합니다.

./lcm << EOF
12
18
EOF

12 와 18 에 대한 예시 출력:

Enter two positive integers:
First number: 12
Second number: 18
The Least Common Multiple of 12 and 18 is: 36

다른 예제를 시도해 보겠습니다.

./lcm << EOF
15
25
EOF

15 와 25 에 대한 예시 출력:

Enter two positive integers:
First number: 15
Second number: 25
The Least Common Multiple of 15 and 25 is: 75

이해해야 할 주요 사항:

LCM 은 두 입력 숫자 모두로 나눌 수 있는 가장 작은 양의 정수입니다.
12 와 18 의 LCM 은 36 입니다.
15 와 25 의 LCM 은 75 입니다.
프로그램은 공식 LCM(a,b) = (a*b)/GCD(a,b) 를 사용합니다.

프로그램을 더욱 안정적으로 만들기 위해 입력 유효성 검사를 추가할 수 있습니다.

nano lcm.c

main() 함수를 업데이트하여 입력 유효성 검사를 포함합니다.

int main() {
    int a, b, lcm;

    printf("Enter two positive integers:\n");
    printf("First number: ");
    scanf("%d", &a);

    printf("Second number: ");
    scanf("%d", &b);

    // 입력 유효성 검사
    if (a <= 0 || b <= 0) {
        printf("Error: 양의 정수만 입력하세요.\n");
        return 1;
    }

    lcm = calculateLCM(a, b);

    printf("The Least Common Multiple of %d and %d is: %d\n", a, b, lcm);

    return 0;
}

업데이트된 프로그램을 다시 컴파일하고 테스트합니다.

gcc lcm.c -o lcm
./lcm

요약

이 실습에서는 C 프로그래밍에서 두 정수의 최소 공배수 (LCM) 를 찾는 방법을 배웁니다. 먼저 사용자 입력으로 두 개의 정수를 읽습니다. 그런 다음 유클리드 알고리즘을 사용하여 최대 공약수 (GCD) 를 계산하는 함수를 만들어 공식 LCM(a,b) = (a*b)/GCD(a,b) 를 구현합니다. 마지막으로 계산된 LCM 을 출력합니다.

핵심 학습 내용은 scanf()를 사용하여 정수 입력을 읽는 것, 유클리드 알고리즘을 사용하여 GCD 를 찾는 것, 그리고 공식을 사용하여 LCM 을 계산하는 것입니다. 이 실습을 마치면 C 에서 두 수의 LCM 을 찾는 방법에 대한 확실한 이해를 얻게 될 것입니다.

C 언어로 최소 공배수 (LCM) 구하기

소개

두 정수 읽기

LCM = (a*b)/GCD(a,b) 사용

LCM 출력

요약