[obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] Número Primo

["Rafael" <cyberhelp@xxxxxxxxxx>]

David,

Se eu entendi bem o que você quer, um método iterativo, há o crivo de
Eratóstenes, de fácil implementação em C++, por exemplo. No caso, você
fornece um número, por exemplo, 7920, e ele retornará todos os primos até
esse número. O algoritmo se baseia numa "peneira": ele vai testando se um
número é primo e, se for, elimina todos os seus múltiplos. Assim, se você
colocar o inteiro posterior ao primo que você quer identificar, 7920, e ele
retornar 7919 como o último primo encontrado, então você terá a confirmação
que desejava. Os únicos inconvenientes desse algoritmo são o gasto de
memória para números grandes e a demora que a resposta pode levar em virtude
do processador utilizado.

Caso seja isso que você quer, posso dar mais detalhes em PVT.


Abraços,

Rafael de A. Sampaio




----- Original Message -----
From: "David" <david-obm@suati.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Wednesday, February 25, 2004 1:34 AM
Subject: [obm-l] RE: [obm-l] RE: [obm-l] Número Primo



>David wrote:
>> Mas tipo, serah q existe algum algoritmo
>> q mude o passo da iteracao para pular alguns
>> numeros durante os testes? Ou eu vo ter q testar
>> 2,3,4,5,6,7,8,...,sqrt(7919) um-a-um mesmo?

> Bem, você não precisa testar todos os números...
> só os primos menores que sqrt(7919) já são suficientes !

Entendi... mas como eu sei que um numero menor que sqrt(7919) eh
primo ou nao pra saber se eu devo testar ele ou nao? Desse jeito
eu acabo tendo q testar todos os menores q sqrt(7919)..

Exemplo: eu tenho q testar se ele eh divisivel por 16, pois eu nao vou
saber se 16 eh primo ou nao antes de testar 16 dividindo 1,2,...,sqrt(16)..
nesse caso seria melhor testar logo de cara se 7919 eh divisivel por 16..

Bem... em todo caso essa dica do sqrt(7919) ja ajuda *muito*..
Obrigado. ;)

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================