소개
이 실습에서는 유클리드 알고리즘을 사용하여 두 정수의 최대 공약수 (GCD) 를 C 프로그램으로 찾는 방법을 배웁니다. 사용자 입력으로 두 정수를 읽은 후 유클리드 알고리즘을 적용하여 그들의 GCD 를 계산하고, 마지막으로 결과를 출력합니다. 이 실습은 수론 및 이산수학의 기본 개념을 다루며, C 프로그래밍 언어를 사용하여 이러한 원리를 실제로 적용하는 방법을 보여줍니다.
두 정수 입력
이 단계에서는 두 정수의 최대 공약수 (GCD) 를 찾기 위해 사용자 입력으로 두 정수를 C 프로그램에서 읽는 방법을 배웁니다.
먼저 GCD 프로그램을 위한 새로운 C 파일을 생성합니다.
cd ~/project
nano gcd.c이제 두 정수를 읽는 다음 코드를 추가합니다.
#include <stdio.h>
int main() {
int num1, num2;
printf("첫 번째 정수를 입력하세요: ");
scanf("%d", &num1);
printf("두 번째 정수를 입력하세요: ");
scanf("%d", &num2);
printf("첫 번째 숫자: %d\n", num1);
printf("두 번째 숫자: %d\n", num2);
return 0;
}코드를 자세히 살펴보겠습니다.
scanf()는 사용자로부터 정수 입력을 읽는 데 사용됩니다.%d는 정수를 위한 형식 지정자입니다.&num1과&num2는 입력을 저장할 변수의 메모리 주소를 전달합니다.
프로그램을 컴파일하고 실행합니다.
gcc gcd.c -o gcd
./gcd예시 출력:
첫 번째 정수를 입력하세요: 48
두 번째 정수를 입력하세요: 18
첫 번째 숫자: 48
두 번째 숫자: 18유클리드 알고리즘 적용
이 단계에서는 두 정수의 최대 공약수 (GCD) 를 찾기 위해 유클리드 알고리즘을 구현합니다.
이전의 gcd.c 파일을 열고 GCD 계산을 포함하도록 수정합니다.
cd ~/project
nano gcd.c유클리드 알고리즘 구현을 포함하여 코드를 업데이트합니다.
#include <stdio.h>
// 유클리드 알고리즘을 사용하여 GCD 를 계산하는 함수
int calculateGCD(int a, int b) {
// 양수로 만드는 과정
a = (a > 0) ? a : -a;
b = (b > 0) ? b : -b;
// 유클리드 알고리즘
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("첫 번째 정수를 입력하세요: ");
scanf("%d", &num1);
printf("두 번째 정수를 입력하세요: ");
scanf("%d", &num2);
// GCD 계산
gcd = calculateGCD(num1, num2);
printf("첫 번째 숫자: %d\n", num1);
printf("두 번째 숫자: %d\n", num2);
printf("최대 공약수: %d\n", gcd);
return 0;
}유클리드 알고리즘 구현을 자세히 살펴보겠습니다.
- 알고리즘은 더 큰 수를 더 작은 수로 반복적으로 나눕니다.
- 나머지를 구하기 위해
%연산자를 사용합니다. - 나머지가 0 이 될 때까지 이 과정을 반복합니다.
- 마지막 0 이 아닌 나머지가 GCD 입니다.
프로그램을 컴파일하고 실행합니다.
gcc gcd.c -o gcd
./gcd예시 출력:
첫 번째 정수를 입력하세요: 48
두 번째 정수를 입력하세요: 18
첫 번째 숫자: 48
두 번째 숫자: 18
최대 공약수: 6GCD 출력
이 단계에서는 GCD 결과를 추가적인 맥락과 함께 포맷하여 출력을 더욱 정보적으로 만듭니다.
이전의 gcd.c 파일을 열고 출력 형식을 추가합니다.
cd ~/project
nano gcd.cGCD 출력을 개선하기 위해 코드를 업데이트합니다.
#include <stdio.h>
// 유클리드 알고리즘을 사용하여 GCD 를 계산하는 함수
int calculateGCD(int a, int b) {
// 양수로 만드는 과정
a = (a > 0) ? a : -a;
b = (b > 0) ? b : -b;
// 유클리드 알고리즘
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("최대 공약수 (GCD) 계산기\n");
printf("------------------------\n");
printf("첫 번째 정수를 입력하세요: ");
scanf("%d", &num1);
printf("두 번째 정수를 입력하세요: ");
scanf("%d", &num2);
// GCD 계산
gcd = calculateGCD(num1, num2);
// 포맷된 출력
printf("\n결과:\n");
printf("첫 번째 숫자: %d\n", num1);
printf("두 번째 숫자: %d\n", num2);
printf("GCD: %d\n", gcd);
// 추가 설명
printf("\n설명:\n");
printf("최대 공약수 (GCD) 는 두 수 모두를 나누어 나머지가 0 이 되는\n");
printf("가장 큰 양의 정수입니다.\n");
return 0;
}프로그램을 컴파일하고 실행합니다.
gcc gcd.c -o gcd
./gcd예시 출력:
최대 공약수 (GCD) 계산기
------------------------
첫 번째 정수를 입력하세요: 48
두 번째 정수를 입력하세요: 18
결과:
첫 번째 숫자: 48
두 번째 숫자: 18
GCD: 6
설명:
최대 공약수(GCD)는 두 수 모두를 나누어 나머지가 0이 되는
가장 큰 양의 정수입니다.주요 개선 사항:
- 제목과 구분자 추가
- 정렬된 열로 출력 포맷 변경
- GCD 개념에 대한 설명 포함
- 핵심 GCD 계산 논리 유지
요약
이 실험에서는 먼저 scanf() 함수를 사용하여 사용자 입력으로 두 개의 정수를 읽는 방법을 배웠습니다. 그런 다음 유클리드 알고리즘을 구현하여 두 수의 최대 공약수 (GCD) 를 계산했습니다. 유클리드 알고리즘은 나머지가 0 이 될 때까지 반복적으로 나머지 연산을 적용하여 GCD 를 효율적으로 찾는 방법입니다. 이때 GCD 는 마지막 0 이 아닌 나머지입니다. 마지막으로 계산된 GCD 를 출력했습니다.
