Primos de Mersenne

[Antonio Donato Filho]

Gerador de numeros Primos que inicia do 2, eu gpostaria de saber se posso iniciar de qualquer numero primo.
Já tentei começar do 214.483647 que é um numero Primo, mas ele gera nyumeros pares.
Alguem?

||| http://pastebin.com/v1nJhrBJ |||

[Nicolas Coelho]

Da maneira que o programa está escrito, ele não tem como identificar os números primos menores do que o número inicial.

O programa não sabe que 2,3,5,7... são primos.

--
--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo quot;Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

Nicolas Zachow Coelho

"Do what you think is interesting, do something that you think is fun and worthwhile, because otherwise you won't do it well anyway." - Brian Kernighan

[Juan Lopes]

Não, não pode. Senão 2 nunca vai ser visto como primo e você vai acabar gerando números que são divisíveis por 2, como você já percebeu que está gerando.

Entretanto, seu algoritmo não está gerando primos de Mersenne, apenas primos comuns. E usar os literais em binário não faz qualquer diferença no desempenho do código.

E chuto que você não esteja chegando ao resultado esperado, pois está adicionando todos os primos entre 2 e 2^61-1 numa lista e não há memória que aguente tudo isso. Por isso você espera que o resultado seja 2^61-1 (que é um Mersenne prime). Mas mesmo assim o seu código está errado, pois você está na verdade tentando pegar o próximo primo apóis 2^61-1 (qualquer primo, não um primo de Mersenne).

De qualquer forma seu código nunca vai chegar lá, do jeito que está escrito.

Se você quer o próximo primo de Mersenne depois de 2^61-1, você tem que usar um teste de primalidade melhor (Miller-Rabin, provavelmente).

--

--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo quot;Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

https://github.com/juanplopes

[Juan Lopes]

Fiz uma versão usando o teste de primalidade de Lucas-Lehmer:

https://gist.github.com/juanplopes/5757bbcf47e956361cb7

Resultado:

2**3-1 is a Mersenne prime

7

---

2**5-1 is a Mersenne prime

31

---

2**7-1 is a Mersenne prime

127

---

2**13-1 is a Mersenne prime

8191

---

2**17-1 is a Mersenne prime

131071

---

2**19-1 is a Mersenne prime

524287

---

2**31-1 is a Mersenne prime

2147483647

---

2**61-1 is a Mersenne prime

2305843009213693951

---

2**89-1 is a Mersenne prime

618970019642690137449562111

---

2**107-1 is a Mersenne prime

162259276829213363391578010288127

---

2**127-1 is a Mersenne prime

170141183460469231731687303715884105727

---

2**521-1 is a Mersenne prime

6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151

---

2**607-1 is a Mersenne prime

531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

---

2**1279-1 is a Mersenne prime

10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087

---

--
https://github.com/juanplopes

[Antonio Donato Filho]

Sim já Pesquisei Lucas-Lehmer Test LLT || http://pastebin.com/Q5MmPdZm || Tem em  Varias linguagens todas sem exeção é super demorado.

Mais valeu pela ajuda.

Grato

Você recebeu essa mensagem porque está inscrito em um tópico no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse tópico, acesse https://groups.google.com/d/topic/python-brasil/2Mn1ZDEHMxU/unsubscribe.
Para cancelar inscrição nesse grupo e todos os seus tópicos, envie um e-mail para python-brasi...@googlegroups.com.

[Antonio Donato Filho]

Esse script aceita um numero diferente de 2.

for i in range(521, 700):

>>> M521 M607