Introdução
Neste laboratório, você aprenderá a encontrar o Máximo Divisor Comum (MDC) de dois inteiros usando o algoritmo de Euclides em um programa C. Você começará lendo dois inteiros da entrada do usuário, em seguida, aplicará o algoritmo de Euclides para calcular seu MDC e, finalmente, imprimirá o resultado. Este laboratório abrange conceitos fundamentais em teoria dos números e matemática discreta, fornecendo uma aplicação prática desses princípios usando a linguagem de programação C.
Ler Dois Inteiros
Neste passo, você aprenderá como ler dois inteiros da entrada do usuário em um programa C para encontrar seu Máximo Divisor Comum (MDC).
Primeiro, vamos criar um novo arquivo C para nosso programa MDC:
cd ~/project
nano gcd.c
Agora, adicione o seguinte código para ler dois inteiros:
#include <stdio.h>
int main() {
int num1, num2;
printf("Digite o primeiro inteiro: ");
scanf("%d", &num1);
printf("Digite o segundo inteiro: ");
scanf("%d", &num2);
printf("Primeiro número: %d\n", num1);
printf("Segundo número: %d\n", num2);
return 0;
}
Vamos analisar o código:
scanf()é usado para ler a entrada de inteiro do usuário%dé o especificador de formato para inteiros&num1e&num2passam os endereços de memória das variáveis para armazenar a entrada
Compile e execute o programa:
gcc gcd.c -o gcd
./gcd
Exemplo de saída:
Digite o primeiro inteiro: 48
Digite o segundo inteiro: 18
Primeiro número: 48
Segundo número: 18
Aplicar o Algoritmo de Euclides
Neste passo, você implementará o algoritmo de Euclides para encontrar o Máximo Divisor Comum (MDC) de dois inteiros.
Abra o arquivo gcd.c anterior e modifique-o para incluir o cálculo do MDC:
cd ~/project
nano gcd.c
Atualize o código com a implementação do algoritmo de Euclides:
#include <stdio.h>
// Função para calcular o MDC usando o algoritmo de Euclides
int calculateGCD(int a, int b) {
// Garantir números positivos
a = (a > 0) ? a : -a;
b = (b > 0) ? b : -b;
// Algoritmo de Euclides
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("Digite o primeiro inteiro: ");
scanf("%d", &num1);
printf("Digite o segundo inteiro: ");
scanf("%d", &num2);
// Calcular o MDC
gcd = calculateGCD(num1, num2);
printf("Primeiro número: %d\n", num1);
printf("Segundo número: %d\n", num2);
printf("Máximo Divisor Comum: %d\n", gcd);
return 0;
}
Vamos analisar a implementação do algoritmo de Euclides:
- O algoritmo divide repetidamente o número maior pelo número menor.
- Ele usa o operador módulo
%para obter o resto. - O processo continua até que o resto se torne 0.
- O último resto não nulo é o MDC.
Compile e execute o programa:
gcc gcd.c -o gcd
./gcd
Exemplo de saída:
Digite o primeiro inteiro: 48
Digite o segundo inteiro: 18
Primeiro número: 48
Segundo número: 18
Máximo Divisor Comum: 6
Print the GCD
In this step, you will format and print the GCD result with additional context to make the output more informative.
Open the previous gcd.c file and add some formatting to the output:
cd ~/project
nano gcd.c
Update the code to enhance the GCD output:
#include <stdio.h>
// Function to calculate GCD using Euclidean algorithm
int calculateGCD(int a, int b) {
// Ensure positive numbers
a = (a > 0) ? a : -a;
b = (b > 0) ? b : -b;
// Euclidean algorithm
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("Greatest Common Divisor (GCD) Calculator\n");
printf("----------------------------------------\n");
printf("Enter the first integer: ");
scanf("%d", &num1);
printf("Enter the second integer: ");
scanf("%d", &num2);
// Calculate GCD
gcd = calculateGCD(num1, num2);
// Formatted output
printf("\nResults:\n");
printf("First number: %d\n", num1);
printf("Second number: %d\n", num2);
printf("GCD: %d\n", gcd);
// Additional explanation
printf("\nExplanation:\n");
printf("The Greatest Common Divisor (GCD) is the largest positive integer\n");
printf("that divides both numbers without leaving a remainder.\n");
return 0;
}
Compile and run the program:
gcc gcd.c -o gcd
./gcd
Example output:
Greatest Common Divisor (GCD) Calculator
----------------------------------------
Enter the first integer: 48
Enter the second integer: 18
Results:
First number: 48
Second number: 18
GCD: 6
Explanation:
The Greatest Common Divisor (GCD) is the largest positive integer
that divides both numbers without leaving a remainder.
Key improvements:
- Added a title and separator
- Formatted the output with aligned columns
- Included an explanation of GCD concept
- Maintained the core GCD calculation logic
Resumo
Neste laboratório, você aprendeu inicialmente a ler dois inteiros da entrada do usuário usando a função scanf(). Em seguida, implementou o algoritmo de Euclides para calcular o Máximo Divisor Comum (MDC) dos dois números. O algoritmo de Euclides é uma forma eficiente de encontrar o MDC aplicando repetidamente a operação módulo até que o resto se torne zero, momento em que o MDC é o último resto não nulo. Finalmente, você imprimiu o MDC calculado.
