Um algoritmo bastante veloz para calcular primos, implementado em C.
O algoritmo é o seguinte: montamos uma tabela em que cada item representa um número. Começamos com a tabela zerada e marcamos 1 em todo número que não for primo. Para isso, basta percorrer a tabela a partir do número 2, e ir marcando todos os múltiplos de cada número com 1, pois, se ele é múltiplo de algum desses números, com certeza não é primo. Quando chegarmos a um número e ele não estiver marcado, significa que ele é primo, pois não é múltiplo de nenhum dos anteriores, caso contrário, estaria marcado. Note que se chegarmos a um número na tabela e ele estiver marcado, podemos pulá-lo: não precisamos marcar seus múltiplos, pois eles já estarão marcados. Afinal, pelo Teorema Fundamental da Aritmética, qualquer número natural pode ser escrito como um produto de números primos.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int tabela[100000];
int main()
{
int i, j;
memset(tabela, 0, sizeof(tabela));
printf("unsigned int primos[] = { 1, ");
for(i = 2; i < sizeof(tabela)/sizeof(int); i++)
{
if(tabela[i])
continue;
for(j = i*i; j < sizeof(tabela)/sizeof(int); j+=i)
tabela[j] = 1;
}
return 0;
}
