Como Implementar o Crivo de Eratóstenes em C

Introdução

Neste laboratório, você aprenderá a implementar o algoritmo de Crivo de Eratóstenes em C para encontrar números primos até um limite superior dado. Você começará lendo o limite superior do usuário, em seguida, marcará os múltiplos dos números primos como não primos e, finalmente, imprimirá todos os números primos encontrados. Este laboratório abrange conceitos em teoria dos números e matemática discreta usando a linguagem de programação C.

O laboratório consiste em três etapas principais: ler o limite superior, marcar múltiplos como não primos e imprimir todos os números primos. Seguindo essas etapas, você obterá uma compreensão mais profunda do algoritmo de Crivo de Eratóstenes e sua implementação em C.

Ler o Limite Superior

Nesta etapa, você aprenderá como ler o limite superior para o algoritmo do Crivo de Eratóstenes em C. O limite superior determina a faixa de números primos que desejamos encontrar.

Primeiro, vamos criar um novo arquivo C para nossa implementação:

cd ~/project
nano prime_sieve.c

Agora, vamos escrever o código inicial para ler o limite superior:

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Digite o limite superior para encontrar números primos: ");
    scanf("%d", &upper_limit);

    printf("Limite superior digitado: %d\n", upper_limit);

    return 0;
}

Compile e execute o programa:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Exemplo de saída:

Digite o limite superior para encontrar números primos: 50
Limite superior digitado: 50

Vamos analisar o código:

Usamos scanf() para ler uma entrada de inteiro do usuário.
O especificador de formato %d informa ao scanf() para ler um inteiro.
Armazenamos a entrada na variável upper_limit.
Em seguida, imprimimos o limite superior digitado para confirmar a entrada.

Marcar Múltiplos como Não Primos

Nesta etapa, você implementará a lógica central do algoritmo do Crivo de Eratóstenes para marcar múltiplos de números primos como não primos.

Vamos modificar o arquivo prime_sieve.c anterior:

cd ~/project
nano prime_sieve.c

Atualize o código para incluir um array e marcar múltiplos:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Digite o limite superior para encontrar números primos: ");
    scanf("%d", &upper_limit);

    // Crie um array booleano para marcar números primos e não primos
    bool is_prime[upper_limit + 1];

    // Inicialize todos os números como primos
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Marque múltiplos de cada número primo como não primos
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Marque múltiplos de p como não primos
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("Marcação de múltiplos completa.\n");

    return 0;
}

Compile e execute o programa:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Exemplo de saída:

Digite o limite superior para encontrar números primos: 50
Marcação de múltiplos completa.

Vamos analisar a lógica do Crivo de Eratóstenes:

Criamos um array booleano is_prime para rastrear números primos e não primos.
Inicialmente, todos os números são marcados como primos.
Iteramos pelos números de 2 até a raiz quadrada do limite superior.
Para cada número primo, marcamos seus múltiplos como não primos.
Iniciamos a marcação de p^2 para otimizar o algoritmo.
O loop interno incrementa em p para marcar todos os múltiplos de p.

Imprimir Todos os Números Primos

Nesta etapa, você completará a implementação do Crivo de Eratóstenes imprimindo todos os números primos encontrados dentro do intervalo fornecido.

Vamos modificar o arquivo prime_sieve.c para adicionar a funcionalidade de impressão:

cd ~/project
nano prime_sieve.c

Atualize o código para imprimir os números primos:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Digite o limite superior para encontrar números primos: ");
    scanf("%d", &upper_limit);

    // Crie um array booleano para marcar números primos e não primos
    bool is_prime[upper_limit + 1];

    // Inicialize todos os números como primos
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Marque múltiplos de cada número primo como não primos
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Marque múltiplos de p como não primos
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // Imprima todos os números primos
    printf("Números primos até %d são:\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

Compile e execute o programa:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Exemplo de saída:

Digite o limite superior para encontrar números primos: 50
Números primos até 50 são:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Vamos analisar as etapas finais:

Após marcar os múltiplos, iteramos pelo array is_prime.
Imprimimos apenas os números que permanecem marcados como primos.
A saída mostra todos os números primos até o limite especificado pelo usuário.

Resumo

Neste laboratório, você aprendeu inicialmente como ler o limite superior para o algoritmo do Crivo de Eratóstenes em C. Você criou um arquivo C, prime_sieve.c, e escreveu código para solicitar ao usuário o limite superior e armazená-lo na variável upper_limit. Em seguida, implementou a lógica central do algoritmo do Crivo de Eratóstenes criando um array booleano para marcar números primos e não primos. Inicializou todos os números como primos e, em seguida, marcou os múltiplos de cada número primo como não primos. Finalmente, você aprenderá como imprimir todos os números primos dentro do limite superior fornecido.