Descomponer un número entero en factores primos en C

Introducción

En este laboratorio, aprenderás cómo descomponer un número entero en sus factores primos utilizando un programa en C. El laboratorio cubre los siguientes pasos:

1. Leer una entrada de número entero del usuario.
2. Implementar un algoritmo para dividir el número de entrada por números primos hasta que esté completamente descompuesto.
3. Imprimir los factores primos del número de entrada.

Al final de este laboratorio, tendrás una mejor comprensión de trabajar con números enteros, números primos y conceptos básicos de programación en C.

Skills Graph

Leer un número entero

En este paso, aprenderás cómo leer una entrada de número entero del usuario en un programa en C para la descomposición en factores primos. Crearemos un programa simple que solicite al usuario que ingrese un número y lo almacene para su posterior procesamiento.

Primero, creemos un nuevo archivo C en el directorio ~/project:

cd ~/project
nano prime_factorization.c

Ahora, agreguemos el siguiente código para leer un número entero:

#include <stdio.h>

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    printf("You entered: %d\n", number);

    return 0;
}

Desglosemos el código:

• #include <stdio.h> incluye la biblioteca estándar de entrada/salida
• int main() es la función principal donde comienza la ejecución del programa
• printf() se utiliza para mostrar una solicitud al usuario
• scanf() lee la entrada de número entero del usuario
• %d es el especificador de formato para números enteros
• &number pasa la dirección de memoria de la variable number

Compila y ejecuta el programa:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Ejemplo de salida:

Enter a positive integer to factorize: 24
You entered: 24

Dividir por números primos hasta descomponer completamente

En este paso, modificarás el programa anterior para implementar el algoritmo de descomposición en factores primos. Actualizaremos el archivo prime_factorization.c para dividir el número de entrada por números primos hasta que esté completamente descompuesto.

Abre el archivo existente:

cd ~/project
nano prime_factorization.c

Reemplaza el código anterior con la siguiente implementación:

#include <stdio.h>

void factorize(int number) {
    printf("Prime factors of %d: ", number);

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        while (number % divisor == 0) {
            printf("%d ", divisor);
            number /= divisor;
        }
    }

    printf("\n");
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Desglosemos el algoritmo de descomposición en factores primos:

• La función factorize() se encarga del proceso de descomposición en factores primos
• Comenzamos con el número primo más pequeño (2)
• El bucle for externo prueba cada posible divisor
• El bucle while interno divide el número repetidamente por el divisor actual
• Imprimimos cada factor primo a medida que lo encontramos
• El número se actualiza mediante división entera en cada iteración

Compila y ejecuta el programa:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Ejemplos de salida:

Enter a positive integer to factorize: 24
Prime factors of 24: 2 2 2 3

Enter a positive integer to factorize: 100
Prime factors of 100: 2 2 5 5

Imprimir factores primos

En este paso, mejorará el programa de descomposición en factores primos para proporcionar una salida más detallada y formateada de los factores primos. Modificaremos el archivo prime_factorization.c existente para mejorar la presentación de los resultados.

Abre el archivo:

cd ~/project
nano prime_factorization.c

Actualiza el código con una función de descomposición mejorada:

#include <stdio.h>

void factorize(int number) {
    int original_number = number;
    int factor_count = 0;

    printf("Prime Factorization of %d:\n", original_number);
    printf("---------------------\n");

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        int current_factor_count = 0;
        while (number % divisor == 0) {
            number /= divisor;
            current_factor_count++;
            factor_count++;
        }

        // Print factors with their exponents
        if (current_factor_count > 0) {
            printf("%d^%d ", divisor, current_factor_count);
        }
    }

    printf("\n\nTotal number of prime factors: %d\n", factor_count);
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Mejoras clave en esta versión:

• Se agregó formato para mostrar los factores primos
• Muestra el exponente de cada factor primo
• Cuenta el número total de factores primos
• Conserva el número de entrada original para su visualización

Compila y ejecuta el programa:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Ejemplos de salida:

Enter a positive integer to factorize: 24
Prime Factorization of 24:
---------------------
2^3 3^1
Total number of prime factors: 4

Enter a positive integer to factorize: 100
Prime Factorization of 100:
---------------------
2^2 5^2
Total number of prime factors: 4

Resumen

En este laboratorio, aprenderás cómo leer una entrada de número entero del usuario, implementar el algoritmo de descomposición en factores primos e imprimir los factores primos del número dado. Los pasos clave incluyen leer el número entero, dividir el número por números primos hasta que esté completamente descompuesto e imprimir los factores primos.

El programa primero solicita al usuario que ingrese un número entero positivo, que luego se almacena en una variable. El algoritmo de descomposición en factores primos se implementa en la función factorize(), donde el número de entrada se divide por números primos hasta que esté completamente descompuesto. Luego, los factores primos se imprimen en la consola.