Numeros Primos

[IwannaC]

Olá amigos

Estava assistindo um seriado Americano chamado 'Numbers' , no episodio 'Prime suspect' mostrava uma prévia do que era a criptografia, um grande número que era todo montado por numeros primos. Achei isso muito interessante, a partir desse ponto surgiu uma dúvida, como posso fazer uma rotina que decomponha um número em fatores primos ?

Obrigado e vlw a atenção !

Aguardo.

[Rafael Schouery (VidaGeek)]

A forma mais simples deve ser gerar todos os primos até n.

Então se n for primo, ele não pode ser decomposto.

Se n não for primo, então você precisa fazer o seguinte: (em pseudo codigo)

n' := n
para cada primo p menor que raiz de n faça
  enquanto n' mod p = 0
     imprima "p "
     n' := n' / p

Falta só achar os numeros primos até raiz de n.

Para isso basta criar a lista começando com dois e percorrer todos os inteiros impares vendo se eles podem ser decompostos (praticamente pelo mesmo algoritmo acima), caso não tenha fatores primos, ele próprio é primo.

[Jonas de Abreu]

Um algoritmo mais eficiente pra gerar todos os numeros primos ate um determinado limite é o Crivo de Erathostenes. O nome é estranho mas o algoritmo é simples.

Primeiro, voce precisa de um vetor (com o mesmo tamanho do seu limite) inicializado com 1 em todas as posicoes.

Segundo, marque a posicao 0 e 1 com 0 (eles não são primos)

Depois comece a percorrer o vetor. Quando encontrar "1", esse numero é primo e você deve tirar todos os multiplos dele. Voce faz isso com um outro laco que comeca em posicao do primo ao quadrado e vai ate o fim do vetor, mas o incremento é a proprio numero primo. Fazendo isso ateh a raiz do limite, voce garante que qualquer posicao que marque "1" no vetor é um numero primo.

De uma olhada neste artigo da wiki http://pt.wikipedia.org/wiki/Erat%C3%B3ste...rat.C3.B3stenes