Como Fatorar um Inteiro em Números Primos em C

Introdução

Neste laboratório, você aprenderá a fatorar um inteiro em seus fatores primos usando um programa em C. O laboratório cobre os seguintes passos:

Ler um inteiro como entrada do usuário.
Implementar um algoritmo para dividir o número de entrada por números primos até que ele seja completamente fatorado.
Imprimir os fatores primos do número de entrada.

Ao final deste laboratório, você terá uma compreensão melhor de como trabalhar com inteiros, números primos e conceitos básicos de programação em C.

Ler um Inteiro

Neste passo, você aprenderá a ler um inteiro como entrada do usuário em um programa C para fatoração de primos. Criaremos um programa simples que solicita ao usuário que digite um número e o armazena para processamento posterior.

Primeiro, crie um novo arquivo C no diretório ~/project:

cd ~/project
nano prime_factorization.c

Agora, adicione o seguinte código para ler um inteiro:

#include <stdio.h>

int main() {
    int number;

    printf("Digite um inteiro positivo para fatorar: ");
    scanf("%d", &number);

    printf("Você digitou: %d\n", number);

    return 0;
}

Vamos analisar o código:

#include <stdio.h> inclui a biblioteca de entrada/saída padrão
int main() é a função principal onde a execução do programa começa
printf() é usado para exibir um prompt ao usuário
scanf() lê a entrada de inteiro do usuário
%d é o especificador de formato para inteiros
&number passa o endereço de memória da variável number

Compile e execute o programa:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Exemplo de saída:

Digite um inteiro positivo para fatorar: 24
Você digitou: 24

Dividir por Primos Até Fatoração Completa

Neste passo, você modificará o programa anterior para implementar o algoritmo de fatoração de primos. Atualizaremos o arquivo prime_factorization.c para dividir o número de entrada por números primos até que ele seja completamente fatorado.

Abra o arquivo existente:

cd ~/project
nano prime_factorization.c

Substitua o código anterior pela seguinte implementação:

#include <stdio.h>

void factorize(int number) {
    printf("Fatores primos de %d: ", number);

    // Começando com o menor número primo
    for (int divisor = 2; divisor <= number; divisor++) {
        while (number % divisor == 0) {
            printf("%d ", divisor);
            number /= divisor;
        }
    }

    printf("\n");
}

int main() {
    int number;

    printf("Digite um inteiro positivo para fatorar: ");
    scanf("%d", &number);

    // Verificação de entrada válida
    if (number <= 1) {
        printf("Por favor, digite um número maior que 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Vamos analisar o algoritmo de fatoração de primos:

A função factorize() lida com o processo de fatoração de primos
Começamos com o menor número primo (2)
O laço for externo tenta cada divisor potencial
O laço while interno divide o número repetidamente pelo divisor atual
Imprimimos cada fator primo à medida que o encontramos
O número é atualizado por divisão inteira em cada iteração

Compile e execute o programa:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Exemplos de saídas:

Digite um inteiro positivo para fatorar: 24
Fatores primos de 24: 2 2 2 3

Digite um inteiro positivo para fatorar: 100
Fatores primos de 100: 2 2 5 5

Imprimir Fatores Primos

Neste passo, você aprimorará o programa de fatoração de primos para fornecer uma saída mais detalhada e formatada dos fatores primos. Modificaremos o arquivo prime_factorization.c existente para melhorar a apresentação dos resultados.

Abra o arquivo:

cd ~/project
nano prime_factorization.c

Atualize o código com uma função de fatoração aprimorada:

#include <stdio.h>

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

    printf("Fatoração de Primos de %d:\n", original_number);
    printf("---------------------\n");

    // Começando com o menor número primo
    for (int divisor = 2; divisor <= number; divisor++) {
        int current_factor_count = 0;
        while (number % divisor == 0) {
            number /= divisor;
            current_factor_count++;
            factor_count++;
        }

        // Imprime fatores com seus expoentes
        if (current_factor_count > 0) {
            printf("%d^%d ", divisor, current_factor_count);
        }
    }

    printf("\n\nNúmero total de fatores primos: %d\n", factor_count);
}

int main() {
    int number;

    printf("Digite um inteiro positivo para fatorar: ");
    scanf("%d", &number);

    // Verificação de entrada válida
    if (number <= 1) {
        printf("Por favor, digite um número maior que 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Melhorias-chave nesta versão:

Adição de formatação para exibir fatores primos
Mostra o expoente de cada fator primo
Conta o número total de fatores primos
Preserva o número de entrada original para exibição

Compile e execute o programa:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Exemplos de saídas:

Digite um inteiro positivo para fatorar: 24
Fatoração de Primos de 24:
---------------------
2^3 3^1
Número total de fatores primos: 4

Digite um inteiro positivo para fatorar: 100
Fatoração de Primos de 100:
---------------------
2^2 5^2
Número total de fatores primos: 4

Resumo

Neste laboratório, você aprenderá a ler um inteiro fornecido pelo usuário, implementar o algoritmo de fatoração de primos e imprimir os fatores primos do número fornecido. Os passos-chave incluem ler o inteiro, dividir o número por números primos até que ele seja completamente fatorado e imprimir os fatores primos.

O programa primeiro solicita ao usuário que digite um inteiro positivo, que é então armazenado em uma variável. O algoritmo de fatoração de primos é implementado na função factorize(), onde o número de entrada é dividido por números primos até que seja completamente fatorado. Os fatores primos são então impressos no console.