Encontrar el Máximo Común Divisor (MCD) en C

Introducción

En este laboratorio, aprenderás a encontrar el Máximo Común Divisor (MCD) de dos enteros utilizando el algoritmo de Euclides en un programa C. Empezarás leyendo dos enteros de la entrada del usuario, luego aplicarás el algoritmo de Euclides para calcular su MCD y, finalmente, imprimirás el resultado. Este laboratorio cubre conceptos fundamentales en teoría de números y matemáticas discretas, proporcionando una aplicación práctica de estos principios utilizando el lenguaje de programación C.

Leer Dos Enteros

En este paso, aprenderás a leer dos enteros de la entrada del usuario en un programa C para encontrar su Máximo Común Divisor (MCD).

Primero, creemos un nuevo archivo C para nuestro programa MCD:

cd ~/project
nano gcd.c

Ahora, agrega el siguiente código para leer dos enteros:

#include <stdio.h>

int main() {
    int num1, num2;

    printf("Ingrese el primer entero: ");
    scanf("%d", &num1);

    printf("Ingrese el segundo entero: ");
    scanf("%d", &num2);

    printf("Primer número: %d\n", num1);
    printf("Segundo número: %d\n", num2);

    return 0;
}

Analicemos el código:

• scanf() se utiliza para leer la entrada de enteros del usuario.
• %d es el especificador de formato para enteros.
• &num1 y &num2 pasan las direcciones de memoria de las variables para almacenar la entrada.

Compila y ejecuta el programa:

gcc gcd.c -o gcd
./gcd

Salida de ejemplo:

Ingrese el primer entero: 48
Ingrese el segundo entero: 18
Primer número: 48
Segundo número: 18

Aplicar el Algoritmo de Euclides

En este paso, implementarás el algoritmo de Euclides para encontrar el Máximo Común Divisor (MCD) de dos enteros.

Abre el archivo gcd.c anterior y modifícalo para incluir el cálculo del MCD:

cd ~/project
nano gcd.c

Actualiza el código con la implementación del algoritmo de Euclides:

#include <stdio.h>

// Función para calcular el MCD usando el algoritmo de Euclides
int calculateGCD(int a, int b) {
    // Asegurar 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("Ingrese el primer entero: ");
    scanf("%d", &num1);

    printf("Ingrese el segundo entero: ");
    scanf("%d", &num2);

    // Calcular el MCD
    gcd = calculateGCD(num1, num2);

    printf("Primer número: %d\n", num1);
    printf("Segundo número: %d\n", num2);
    printf("Máximo Común Divisor: %d\n", gcd);

    return 0;
}

Analicemos la implementación del algoritmo de Euclides:

• El algoritmo divide repetidamente el número mayor por el número menor.
• Utiliza el operador módulo % para obtener el resto.
• El proceso continúa hasta que el resto se convierte en 0.
• El último resto no nulo es el MCD.

Compila y ejecuta el programa:

gcc gcd.c -o gcd
./gcd

Salida de ejemplo:

Ingrese el primer entero: 48
Ingrese el segundo entero: 18
Primer número: 48
Segundo número: 18
Máximo Común Divisor: 6

Imprimir el MCD

En este paso, formatearás y mostrarás el resultado del MCD con contexto adicional para que la salida sea más informativa.

Abre el archivo gcd.c anterior y añade algo de formato a la salida:

cd ~/project
nano gcd.c

Actualiza el código para mejorar la salida del MCD:

#include <stdio.h>

// Función para calcular el MCD usando el algoritmo de Euclides
int calculateGCD(int a, int b) {
    // Asegurar 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("Calculadora de Máximo Común Divisor (MCD)\n");
    printf("----------------------------------------\n");

    printf("Ingrese el primer entero: ");
    scanf("%d", &num1);

    printf("Ingrese el segundo entero: ");
    scanf("%d", &num2);

    // Calcular el MCD
    gcd = calculateGCD(num1, num2);

    // Salida formateada
    printf("\nResultados:\n");
    printf("Primer número:  %d\n", num1);
    printf("Segundo número: %d\n", num2);
    printf("MCD:           %d\n", gcd);

    // Explicación adicional
    printf("\nExplicación:\n");
    printf("El Máximo Común Divisor (MCD) es el entero positivo más grande\n");
    printf("que divide ambos números sin dejar resto.\n");

    return 0;
}

Compila y ejecuta el programa:

gcc gcd.c -o gcd
./gcd

Salida de ejemplo:

Calculadora de Máximo Común Divisor (MCD)
----------------------------------------
Ingrese el primer entero: 48
Ingrese el segundo entero: 18

Resultados:
Primer número:  48
Segundo número: 18
MCD:           6

Explicación:
El Máximo Común Divisor (MCD) es el entero positivo más grande
que divide ambos números sin dejar resto.

Mejoras clave:

• Se añadió un título y un separador.
• Se formatea la salida con columnas alineadas.
• Se incluye una explicación del concepto de MCD.
• Se mantiene la lógica central del cálculo del MCD.

Resumen

En este laboratorio, aprendiste primero cómo leer dos enteros de la entrada del usuario utilizando la función scanf(). Luego, implementaste el algoritmo de Euclides para calcular el Máximo Común Divisor (MCD) de los dos números. El algoritmo de Euclides es una forma eficiente de encontrar el MCD aplicando repetidamente la operación módulo hasta que el resto se convierta en cero; en ese punto, el MCD es el último resto no nulo. Finalmente, imprimiste el MCD calculado.