Como Encontrar o Máximo Divisor Comum (MDC) em C

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
&num1 e &num2 passam 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.