Re: Programa para achar nºs primos ...

["Juliana Freire" <jufreire@xxxxxxxxxxxxxx>]

Isso é muito simples.
Claro que quanto mais primos você quiser mais tempo vai demorar para rodar, porque como foi mencionado, eles ficam mais esparsos.
Coloque no MAX_PRIMOS o número de primos que você quer achar, este programa vai começar do 2.

A idéia é a seguinte:
2 é primo. Cria uma caixinha com o número 2.
Os próximos números vão tentar passar pela caixinha, mas só vão conseguir aqueles que não forem divisíveis por 2.
O 3 passa. Como só tinha uma caixinha, ele passou por todas as caixinhas então ele é primo. Cria uma caixinha para ele. Você vai
criando uma fila de caixinhas.
Os números vão passando pela fila, e quando eles passam por algum número que eles são divisíveis, eles param. Quem consegue passar
pela fila inteira é porque não era divisível por ninguém, ou seja, é primo. E aí ele ganha uma caixinha nova também...

Não sei se expliquei direito. Aí vai o código:
Ele coloca os números primos no vetor "primos".

***********************************************************

#define MAX_PRIMOS 100000

int primos[MAX_PRIMOS];
int nprimos;
primos[0] = 2;
nprimos = 1;
int i = 3;
int n,j;
do
{
  n = i;
  for (j=0;j<nprimos;j++)
     while (n%primos[j] == 0)
       n /= primos[j];
  if (n != 1)
  {
    primos[nprimos] = n;
    nprimos ++;
  }
  i+=2;
} while (nprimos < MAX_PRIMOS);