C 프로그래밍에서 GCD 찾기

소개

C 프로그래밍에서 GCD (최대공약수, Greatest Common Divisor) 는 자주 계산됩니다. GCD 를 찾는 데 일반적으로 두 가지 방법이 사용됩니다. 유클리드 알고리즘을 사용하거나, 반복적인 뺄셈을 통해 GCD 를 계산할 수 있습니다. 이 단계별 랩에서는 두 가지 방법을 모두 시연할 것입니다.

유클리드 알고리즘 사용

유클리드 알고리즘은 분자를 나눗셈 연산의 나머지로 대체하여 GCD 를 계산하는 데 사용됩니다. 나머지가 0 이 되면, GCD 는 분자가 됩니다.

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 마지막으로, 두 숫자의 GCD 를 표시합니다.

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

반복 뺄셈 방법 사용

이 방법에서는 두 값이 같아질 때까지 더 작은 값을 더 큰 값에서 반복적으로 빼서 GCD 를 계산합니다. 두 값이 같아지면, 해당 숫자가 GCD 입니다.

2.1 0 으로 초기화된 num 이라는 정수 변수로 시작합니다.

    int num = 0;

2.2 x 라는 정수 변수를 선언하고 2 로 초기화합니다.

    int x = 2;

2.3 사용자에게 GCD 를 구할 정수의 개수를 입력하도록 요청합니다.

    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 를 계산할 수 있습니다. 입력 값의 GCD 를 계산하기 위해 gcd() 함수를 호출합니다.

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

방법 결합

이 단계에서는 구현을 완료하기 위해 방법을 결합합니다.

3.1 반복 뺄셈 방법으로 GCD 를 찾는 데 사용할 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)    // infinite loop to take input
    {
        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 를 계산하는 두 가지 방법, 즉 유클리드 알고리즘 (Euclidean algorithm) 과 반복 뺄셈 방법 (repeated subtraction method) 을 배웠습니다. 자세한 설명과 예제 코드 블록을 통해 이러한 방법을 사용하는 방법을 시연했습니다. 더 나은 이해를 위해 main.c 파일에서 코드를 수정하고 실행해 보는 것이 좋습니다.