O crivo de Eratóstenes – Um método para encontrar números primos.

O Problema:

Um inteiro primo é qualquer inteiro que só pode ser dividido exatamente por si mesmo e por 1. O Crivo de Eratóstenes é um métodos de encontar números primos. Ele funciona da seguinte maneira:

a) Crie um array com todos os elementos inicializados com 1 (verdadeiro). Os elementos do array com subscritos primos permanecerão 1. Todos os outros elementos do array serão definidos  como zero.

b) Começando com o subscrito 2 do array (o subscrito 1 deve ser primo), sempre que for encontrado um elemento do array cujo valor seja 1, faça um laço pelo restante do array e defina como zero todos os outros elementos cujo subscrito seja múltiplo do subscrito com valor 1. Para o subscrito 2 do array, todos os elementos além de 2 que forem múltiplos de 2 serão definidos como zero (subscritos 4, 6, 8, 10 etc.). Para o subscrito 3 do array, todos os elementos além de 3 que forem múltiplos de 3 serão definidos como zero (subscrito 6, 9, 12, 15 etc.).

Quando esse processo for concluído, os elementos do array que ainda estiverem definidos como 1 indicam que o subscrito é um número primo. Esses subscritos podem ser impressos.

A Solução:

Esse problema possui uma solução muito fácil de ser implementada. Um algoritmo para resolver esse problema pode ser assim:

{Objetivo: usar o método do Crivo de Eratóstenes para achar números primos}
Algoritmo Crivo_de_Eratóstenes
{cria um vetor de inteiros de tamanho max}
    Inteiro[max] primos;
    
    {Inicializa todos os elementos com 1}
    Para i = 1 até max
        primos[i] = 1;
        i = i + 1;
    {Anula os elementos do array que não são primos}
    Para i = 2 até max
        Se primos[i] == 1
            {Função para anular os múltiplos de i}
            AnulaMultiplos(i);
    {Função para imprimir o subscrito do array quando o elemento do array naquele subscrito é igual a 1}
    ImprimePrimos();
}

Como dá pra perceber o algoritmo é bastante simples, vamos implementar em linguagem C++ esse algoritmo:

#include iostream.h
#include stdlib.h
void imprimePrimos(int primo[], int max);
void anulaMultiplos(int primo[], int max, int subscrito);
int main()
{
    const int max = 10000;
    int primo[max];
    for (int i = 1; i < max; i++)
        primo[i] = 1;
    for (int i = 2; i < max; i++)
        if (primo[i] == 1)
            anulaMultiplos(primo, max, i);
        imprimePrimos(primo, max);
    system("PAUSE");
    return 0;
}
void anulaMultiplos(int primo[], int max, int subscrito)
{
    for (int i = subscrito; i = max)
            break;
        else
            primo[i * subscrito] = 0;
}
void imprimePrimos(int * primo, int max)
{
    for (int i = 0; i < max; i++)
        if (*(primo + i) == 1)
            cout << i << "\t";
        cout << "\n";
}

Nesse caso esse programa gera os números primos até 10000, já que este é o valor de max. Para gerar mais números primos basta mudar esse valor.

Tags:

Uma resposta to “O crivo de Eratóstenes – Um método para encontrar números primos.”

  1. rafael Says:

    Brigado pelo post me ajudo muito na resolução de um exercicio

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s


%d blogueiros gostam disto: