numeros primos

Universidade Federal de Minas Gerais – Pampulha
Ciências da Computação

Documentação TP1

Trabalho apresentado à disciplina
Organização de Computadores I

Leonel Fonseca Ivo – 2007041418

Março/2008
Números Primos

Algoritmo utilizado (linguagem C):

#include

/*Implementa o Crivo de Eratóstenes para a identificação dos primos*/
/*Parametro: Vetor com os numeros cujas primalidades serão verificadas*/ int testa_primo (int *crivo, int n)
{
int salto; //Modo de caminhar no vetor int i; //Contadores //A primeira posicao do crivo (posicao 0) contera sempre o numero
//2, portanto, a posicao de um inteiro 'n' no crivo e exatamente
//n-2
if (n > 1 && crivo[n - 2] != 0) { salto = n; //Zera todos os multiplos de 'n' no crivo for (i = n + salto; i < 1000; i += salto) crivo[i-2] = 0; return 1; //'n' e primo } return 0;
}

int main ()
{
int i, n; int *primos; //Vetor que 'simula' o Crivo de Eratostenes int total = 0; //Interrompe execucao ao encontrar os 100 //primeiros primos primos = malloc (sizeof(int *) * 1000); n = 2; //Primeiro numero do Crivo //Monta Crivo de Eratóstenes comecando de 2 e indo ate 1002 for (i = 0; i < 1000; i++) { primos[i] = n; n++; } for (i = 0; i < 1002; i++) { if (testa_primo (primos, i) == 1) { printf ("%d e primo\n", primos[i-2]); total++; } if (total == 100) break; n++; } printf ("total primos: %d\n", total);
}

Explicação sobre o algoritmo

O algoritmo utiliza-se do Crivo de Eratóstenes para encontrar os cem primeiros números primos. Esse método funciona da seguinte maneira: monta-se uma lista com os números naturais de 1 a ‘n’; começa-se marcando o número 2 (primeiro primo), cortando-se da lista todos os seus múltiplos; marca-se o próximo número não eliminado (3) e também elimina-se todos os seus múltiplos da lista;