Teorema Becker - Gerador Numeros Primos em Python 3

[Matrix Matematica]

Boa tarde a todos!

venho a divulgar uma teoria matemática na qual trabalhei por mais de 10 anos,relacionada aos numeros primos,para prová-la desenvolvi um programa em Python 3 que usa apenas minha teoria para gerar tais numeros. não sou programador,mas creio que seja o algoritmo mais rapido do mundo para tal,mas é óbvio que pode ser melhorado e muito por programadores de verdade.

segue link do programa: https://drive.google.com/file/d/0B-VoQj7RjQ9nR3VLdjdSS3VFXzg/view?usp=sharing

e do video do youtube postado hoje para divulgação do teorema: https://youtu.be/DDSiqZ1yEBw

Obrigado pela atenção.

[Henr"Ikke" Pereira]

Olá Bruno,

Não desmerecendo tua teoria, mas teu algoritmo me parece bem mais lento que o Crivo de Eratóstenes.

Rodando 2000 ciclos do teu algoritmo, eu consigo chegar no primo 83987 e leva algo em torno de 8 segundos no meu PC.

Enquanto usando o Crivo, eu consigo calcular os primos até 1000000 em menos de 0.5s [1].

[1] http://ideone.com/YTaMB

--
--
------------------------------------
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 "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.

--

Henrique G.G. Pereira - "Ikke"

+1 (530) 637-8731

http://www.orkuts.com.br

[Bruno Becker]

Boa noite. Ta desmerecendo não,meu programa ta muitooooooo pesado,eu sei disto. como esta na descrião do video eu não sou programador,fiz este programa apenas para provar minha teoria,e pelo meno pra isto creio que ele funcione bem né?rsrsrs

O mais importante pra mim é a teoria matematica da coisa,e se está certa. 

Mas se alguem quiser brincar com esta teoria creio que conseguirá resultados bem melhores que o crivo de Erastôtenes,é eu que sou ruim programador mesmo,kkkkk

Fica uma dica, (b) se resume apenas a semi-primos divisiveis por primos maiores que 11 e a primos.

Outra dica, fatorar (b) pelo resultado de todos (b),ao invés de fatorar por numeros impares(eu não consegui fazer isto no programa,rsrs).

Outro fato que pesa ele é o de ele somar 42 a cada variavel,não consegui somar 42 de uma vez a chave toda(viu como não sei programar,kkkkk).

Mas a teoria matematica é interessante né?Pelo menos eu acho.

Qualquer duvida estou ai(desde que não seja sobre programação,rsrsrs).

[Bruno Becker]

Bom dia Henrique. Fiquei com sua crítica construtiva mastelando minha cabeça a noite toda,kkkkkkkk  É óbvio que meu programa ta pesado demais,tem muitas variaveis,que poderiam ser reduzidas com certeza(por alguem que saiba programar,rsrs),mas hj entrei no link do crivo que vc postou,e rodei ele aqui,e de fato ele mostrou o resultado em menos de 1 segundo no meu celeron que comprei nas casas bahia,rsrsrs,mas ele só deu um resultado (78498) que imagino ser o numero de digitos do ultimo primo gerado por ele... Mas convenhamos que este programa que vc passou não esta trabalhando de fato,mostrando todos numeros primos na tela e salvando em .txt igual ao meu,rsrsrs  gostaria de saber o tempo de execução dele fazendo o mesmo que o meu faz,sei que vai ser mais rapido,mas quanto mais rapido?

Eis a questão.

Não sei programar,mas estou tentando aprimorar meu alg,se alguem quiser ajudar com idéias,ficarei muito grato. Pois até que alguem prove que a teoria matematica ta errada(coisa que duvido...) vou continuar cozinhando a teoria,rsrsr

Em quarta-feira, 29 de abril de 2015 17:28:06 UTC-3, Henrique G.G. Pereira escreveu:

[Welton Vaz]

Prezado amigo,

Eu sou um fanático por números primos, e achei sua ideia muito boa.

Mas tem como vc explicar, melhor? Porque a formula: (x)= (p/42)-r gera um numero fracionário negativo?

Enviado com MailTrack

Welton Vaz de Souza
TWITTER: http://twitter.com/Weltonvaz
BLOG: http://ghandybh.blogspot.com/

FACEBOOK: https://www.facebook.com/weltonv
Cel: (31)9327-0823



Bonito é melhor que feio.
Explícito é melhor que implícito.
Simples é melhor que complexo.
Complexo é melhor que complicado.
Plano é melhor que aninhado.
Esparso é melhor que denso.
Legibilidade conta.
Casos especiais não são especiais o bastante para se quebrar as regras.
Embora a simplicidade supere o purismo.
Erros nunca deveriam passar silenciosamente.
A menos que explicitamente silenciados.
Ao encarar a ambiguidade, recuse a tentação de adivinhar.
Deveria haver uma – e preferencialmente apenas uma – maneira óbvia de se fazer isto.
Embora aquela maneira possa não ser óbvia à primeira vista se você não for holandês.
Agora é melhor que nunca.
Embora nunca, seja muitas vezes melhor que pra já.
Se a implementação é difícil de explicar, é uma má idéia.
Se a implementação é fácil de explicar, pode ser uma boa idéia.
Namespaces são uma idéia estupenda – vamos fazer mais deles!
***********************************************************

 °v° NÃO USE DROGAS,
/(_)\ USE GNU/LINUX
 ^ ^

[Bruno Becker]

Novo link download programa,BEMMMM MAIS RÁPIDO. alterei a fatoração,o limite agora é a raiz quadrada de cada numero de (b),pois:
"Todo composto tem pelo menos um fator menor ou igual a raiz quadrada dele "

Claro que pode ser melhorado e muito,diminuindo as variaveis,segue o link:

https://drive.google.com/file/d/0B-VoQj7RjQ9nZkFZcXdrbkRYbEE/view?usp=sharing

[Juan Lopes]

Engraçado que eu comentei sobre o assunto ontem mas aparentemente meu post não foi para o grupo.

Bruno, sua teoria não é nova, tampouco é capaz de melhorar as estratégias atuais para geração de números primos.

Basicamente o que você diz é que todo número primo p>42 pode ser escrito como p=b+(x*42), onde b é um de um conjunto de 12 números. Isso nada mais é do que uma outra versão da observação (deveras trivial) de que todo número primo pode ser escrito na forma 6k±1, um resultado amplamente conhecido.

Aprecio seu interesse por matemática, mas você precisa trabalhar melhor a sua base teórica antes de fazer uma descoberta realmente útil, que mereça o trabalho de "registrar em cartório".

--

--
------------------------------------
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 "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

[Fabio C. Barrionuevo da Luz]

Você poderia enviar o seu artigo/tese/dissertação que inclua o texto em que você defende e prova a sua teoria e que também as referências bibliográficas e em quais revistas/eventos a sua teoria foi aceita.

Eu gostaria de lê-la na íntegra.

__
Fábio C. Barrionuevo da Luz Acadêmico de Sistemas de Informação na Faculdade Católica do Tocantins - FACTO Palmas - Tocantins - Brasil - América do Sul

http://pythonclub.com.br/

Blog colaborativo sobre Python e tecnologias Relacionadas, mantido totalmente no https://github.com/pythonclub/pythonclub.github.io .

Todos são livres para publicar. É só fazer fork, escrever sua postagem e mandar o pull-request.
Leia mais sobre como publicar em README.md e contributing.md.
Regra básica de postagem: "Você" acha interessante? É útil para "você"? Pode ser utilizado com Python ou é útil para quem usa Python? Está esperando o que? Publica logo, que estou louco para ler...

[Bruno Becker]

deixa eu rir primeiro,haha.

Mas não gostei do seu tom...

Primeiramente,vc esta me julgando muito mal,com poucas informações sobre mim,e sobre MINHA teoria.

Eu pesquiso isso ha mais de 10 anos,e vc acha que não sei sobre o fato de  "que todo número primo pode ser escrito na forma 6k±1"...

Isso tem a ver e muito com minha teoria,sim...mas..

Você sabe o PQ "de que todo número primo pode ser escrito na forma 6k±1"?

Eu só contei o fim do filme sabe... sabe aqueles filmes que começam com o fim,pra depois mostrar"tantos anos antes...",bom eu fiz isso.

pra vc ter idéia a base da minha teoria é um conjunto ciclico que pode ser escrito de forma binéria ou boolena(vc que escolhe,eis ele:

xoxooxxoxxoxxoxxooxox ou se preferir: 101001101101101100101

Ja vc que é o estudado e sabe TUDO sobre a farsa da minha teoria,conta pra gente oque significa isso...(coisa que eu vou explicar nos futuros videos,como ja disse...).

Sim 6k±1 é a complicação da minha teoria,e não o inverso...

Pois sei que qualquer matemático vai usar um monte de equações "extraterrestres",pra explicar(se é que vai explicar) o PORQUE 6k±1 é assim...

Ja dizia Jesus,não julgueis para não serdes julgados,vc veio com um tom agressivo,perjorativo,e recebeu o mesmo,não reclame.

[Pedro Werneck]

Bruno,

Não vejo a resposta do Juan Lopes como depreciativa. Seria
depreciativo atribuir ao seu trabalho um valor menor do que merece,
mas acho que você superestima o que fez e por isso entendeu a crítica
como depreciativa.

Se você realmente acredita que descobriu algo revolucionário, o
caminho correto é procurar uma publicação acadêmica que esteja
disposta a publicar um artigo com sua teoria, e ver o que outros
experts no assunto tem a dizer a respeito. Registrar algo em cartório,
gravar vídeos, fazer alegações em listas de discussão sobre outro
assunto e hostilizar os críticos não é a forma correta de fazer isso.
Talvez você precise de alguma orientação acadêmica.

Portanto, como moderador, peço que leve a discussão sobre a sua teoria
para uma lista sobre Matemática, e aqui foque apenas no seu código
Python. Também agradeço imensamente se puder resolver suas diferenças
com o Juan Lopes em privado.

---
Pedro Werneck

[Juan Lopes]

Todo primo pode ser escrito como 6k±1, por que no anel comutativo Z₆ ({0̅, 1̅, 2̅, 3̅, 4̅, 5̅}), somente 1 e 5 possuem inverso multiplicativo. E -1 ≡ 5 mod 6.

Isso significa dentre os possíveis restos da divisão inteira do número por 6, somente 1 e 5, não tornam o número trivialmente composto.

6k + 0 é divisível por definição

6k + 2 é par

6k + 3 é divisível por 3

6k + 4 é par

Outra forma de ver é que somente 1 e 5 são válidos pois são os únicos cujo gcd(_, 6) = 1 (ou seja, que não compartilham nenhum divisor com 6).

No seu "teorema", os tais 12 números que você encontrou são todos os elementos em Z₄₂ que não compartilham nenhum divisor com 42.

Você pode derivar esses 12 números mágicos com esse script em Python

def gcd(a, b): 

    return gcd(b, a % b) if b else a

print(list(filter(lambda n: gcd(42, n)==1, range(42))))

#[1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]

Algebricamente falando, os seus 12 números são os únicos que possuem inverso multiplicativo no anel comutativo Z₄₂.

Quando à minha forma de falar, eu acredito ter sido. Deixei claro que aprecio seu interesse pela matemática, mas você precisa focar em entender a teoria existente antes de criar a sua. Mas se você espera condescendência das pessoas (o que não tem problema nenhum se você é um iniciante), tenha pelo menos a humildade de não chegar pagando de expert no assunto.

[Bruno Becker]

Em primeiro lugar,mil desculpas ao Juan,e a todos pela conversa desagradavel da minha parte,e minha ignorância.

Acho que postei minha teoria no lugar errado,pois como esta escrito na descrição do video(desde quando postei), não sou programador e nem matemático,sou um ocultista,ou seja deveria ter postado em alguma comunidade sobre cabalá e afins...

Mas vim aqui pedir uma ajuda na programação,pois como esta escrito na descrição do video eu só aprendi o suficiente pra provar minha teoria,pois um computador é imparcial.

Creio sim que acrescentei algo a matemática,pois pensemos comigo:

Se alguem no mundo ja tivesse correlacionado o numero 42 da forma que eu fiz aos numeros primos,ja não teriam escrito sobre isso na internet?(pois todo mundo sabe que ele é um numero famoso entre "nerds" e afins...)

Desafio alguem mostrar algum site na internet,até mesmo em russo ou chines,que mostre algo igual ao que estou mostrando...

Como disse,só mostrei o resultado da teoria,mas não como cheguei nela,e garanto que é muito fascinante(postarei video em breve) no sentido filosófico e mistico.

Novamente desculpas,e ninguem aqui contribuiu em nada no quesito programação,uma pena,terei que continuar quebrando a cabeça sozinho...

Não voltarei a postar mais aqui,e se quiser pode excluir-me do grupo e minhas postagens(pois a internet é bem grande).

Mas Pedro,peço que pra terminar está historia seja postado esta minha resposta,e depois apague o que quiser....

Sobre eu seguir o metodo academico para publicar minha teoria,isso não vai acontecer,pois não sou matematico.

Mas foi assim com todo mundo né,com Tesla,e outros...

Quem quiser continuar suas criticas,fique a vontade no meu canal no youtube,serão bem vindas.

Fui.

[Henr"Ikke" Pereira]

2015-04-30 14:49 GMT-03:00 Bruno Becker <bbecke...@gmail.com>:

Em primeiro lugar,mil desculpas ao Juan,e a todos pela conversa desagradavel da minha parte,e minha ignorância.

Acho que postei minha teoria no lugar errado,pois como esta escrito na descrição do video(desde quando postei), não sou programador e nem matemático,sou um ocultista,ou seja deveria ter postado em alguma comunidade sobre cabalá e afins...

Mas vim aqui pedir uma ajuda na programação,pois como esta escrito na descrição do video eu só aprendi o suficiente pra provar minha teoria,pois um computador é imparcial.

Creio sim que acrescentei algo a matemática,pois pensemos comigo:

Se alguem no mundo ja tivesse correlacionado o numero 42 da forma que eu fiz aos numeros primos,ja não teriam escrito sobre isso na internet?(pois todo mundo sabe que ele é um numero famoso entre "nerds" e afins...)

Desafio alguem mostrar algum site na internet,até mesmo em russo ou chines,que mostre algo igual ao que estou mostrando...

http://mathforum.org/kb/message.jspa?messageID=7818529

--

Henrique G.G. Pereira - "Ikke"

+1 (530) 637-8731

+55 (55) 9619-7499

http://www.orkuts.com.br

[flit]

HeadShot!

[]s

Henrique

Ps. Rolou um Ademir feeling

[Diego Rocha]

Bem, caso encerrado... Próooooximo

[Daniel Viana Auler]

Pessoal,

   Acho que o intuito do cara é ajuda ao implementar o algoritmo em python, se ele passou 10 anos estudando algo, e alguém não concorda com isso, acho que não tem nada haver discutir isso aqui, ele pediu ajuda, e os metidos a sabichões que não sabem nada resolveram criticar. Toda teoria é válida, mas é uma teoria até que seja comprovada, ela se baseia em hipóteses, não faz sentido um retardado achar que manja mais que um cara que estuda isso a 10 anos, e pior ele não pediu opinião, tu deu de graça ta e ai sábio, vai ajudar o cara a melhorar o código python ou vai ficar só falando mal, eu acho que tu não manja nada e quer se afirmar como inteligente falando besteira do trabalho dos outros.

Att,

Daniel Viana Auler
dan...@dvasolucoes.com.br
Tel/Fax: 51-30858550
Cel: 51-81313458
DVA Soluções em TI

[Pedro Werneck]

Bruno,

OK, agora sua intenção ficou mais clara. Eu estudo simbolismo e
religiões comparadas, e se você chegou a essa conclusão sobre
primalidade a partir do número 42 por guematria ou outro método ou
hermenêutica puramente simbólico e não-matemático -- que não é o que
você mostrou aqui -- eu até me interesso em ver os detalhes, mas por
favor, em texto, não em vídeo.

Se você queria provar que sua descoberta é válida matematicamente
através do código, já está claro que isso não é necessário, pois a
própria prova matemática é trivial. Sua atitude em apresentar algo
trivial como teorema matemático como e uma descoberta revolucionária
depõe contra você, pois você mesmo tinha obrigação de saber isso
antes. Tome como exemplo o maior gênio do simbolismo no século XX,
René Guénon, que era um matemático brilhante antes de ingressar nos
movimentos ocultistas da França e nos estudos doutrinais.

Não vou te remover da lista ou excluir suas postagens porque você
reconheceu o erro na sua atitude e explicou melhor suas intenções, mas
aqui realmente não é o lugar para isso. Se alguém quiser ajudar a
melhorar o código, fique à vontade.

[Pedro Werneck]

Daniel,

Esse seu comentário foi totalmente desnecessário. Eu pedi que o
próprio Bruno Becker resolvesse qualquer problema pessoal com o Juan
em privado para evitar esse clima de hostilidade na lista, e você está
fazendo o mesmo com outro.

Considere isso uma advertência.

[Pedro Werneck]

Pessoal,

Peço que participem do tópico apenas para colaborar com o código do
Bruno. A discussão da teoria dele é um assunto completamente off-topic
nessa lista.

--
---
Pedro Werneck

[Diego Rocha]

Daniel,

Não vi as primeiras mensagens do Juan como agressivas, quem subiu o tom foi o autor.

Concordo com você que qualquer teoria é válida, mas ele estava SUPERestimando a própria teoria.
Primeiro falando que seria o algoritmo mais rápido existente, depois falando que ninguém tinha achado a mesma propriedade daquele conjunto de números.

As duas afirmações foram negadas através de contra-exemplo, pelo que me lembro das aulas de Álgebra um contra-exemplo é válido para refutar uma teoria (embora um exemplo não a comprove, é necessário provador "para todo", por indução, ou absurdo).

Eu sei que o foco da lista é Python e que deveríamos focar em ajudar ele em refatorar o código, mas uma parcela grande dos membros da lista é formada por acadêmicos (ou por programadores que gostam de matemática, como eu), então discutir a base de teoria que aparece é inevitável.

Atenciosamente,
Diego Rocha

[Diego Rocha]

Pedro Weneck, me desculpe, escrevi o último e-mail que enviei antes de ver esse seu.

Atenciosamente,
Diego Rocha

[Daniel Viana Auler]

Não sei se ajuda, mas já havia percebido que cada print em qualquer programa python ele gera um tempo desnecessário no código, rodei 2000 ciclos em 0.18 utilizando o código limpo apenas dessa forma(rodo windows xp,quadricore, 4gb ram):

import math

print(" TEOREMA BECKER - GERADOR DE NUMEROS PRIMOS ")

print(" ")

ciclo = int(input("Digite numero de ciclos: "))

import time

t0=time.time()

hora_start=time.localtime()[3]

minuto_start=time.localtime()[4]

contador = 0

nbase1 = 1

nbase2 = 5

nbase3 = 11

nbase4 = 13

nbase5 = 17

nbase6 = 19

nbase7 = 23

nbase8 = 25

nbase9 = 29

nbase10 = 31

nbase11 = 37

nbase12 = 41

while ciclo > contador:  

  todosbase=[nbase1,nbase2,nbase3,nbase4,nbase5,nbase6,nbase7,nbase8,nbase9,nbase10,nbase11,nbase12]

  primos=[nbase1,nbase2,nbase3,nbase4,nbase5,nbase6,nbase7,nbase8,nbase9,nbase10,nbase11,nbase12]

  for todosbase in todosbase:

    sqrt = (todosbase ** 0.5)

    for i in range (3,int(sqrt) + 1,2):

      

       if(todosbase%i == 0): 

           primos.remove(todosbase)           

           if (todosbase==todosbase):

             break

  nbase1= nbase1+42

  nbase2= nbase2+42

  nbase3= nbase3+42

  nbase4= nbase4+42

  nbase5= nbase5+42

  nbase6= nbase6+42

  nbase7= nbase7+42

  nbase8= nbase8+42

  nbase9= nbase9+42

  nbase10= nbase10+42

  nbase11= nbase11+42

  nbase12= nbase12+42

  contador = contador+1

print t0-time.time()

[Henr"Ikke" Pereira]

http://pastebin.com/g303SmUH

Esse roda até o ciclo 2000 em ~0.12, até o 5000 em ~0.44, até o 15000 em 2.1s e até o 20000 em 3.0s

[Daniel Viana Auler]

Fiz o seguinte teste, peguei o código da teoria becker e peguei o da teoria crivo da seguinte forma:

import sys

import time

primes=[2, 3]

 

i, j, k = 5, 0, 0

print "TEOREMA CRIVO"

t0=time.time()

while i<83987:

 

   j = 0

   k = i**(0.5)

 

   while primes[j]<k and i%primes[j]:

      j += 1

   if primes[j]>k:

      primes += [i]

   if i%3==2:

      i+=2

   else:

      i+=4

 

print t0-time.time()

código do becker:

nos 10 testes que rodei o Crivo dava 0.18 e o Becker 0.17

se a teoria de crivo tem mais de 2 mil anos e essa do cara tem apenas 10 e ele conseguiu se igualar ou ser 5% mais rápido, já é algo hein.

[Welton Vaz]

Amigos,

Vcs já ouviram falar do teste de primalidade MillerRabin, http://goo.gl/oPQ5BE com ele vc consegui 2000 números primos em 

5 segundos.

Codigo aqui: http://pastebin.com/ZZvFyhqM

Enviado com MailTrack

[Linux - Junior Polegato]

On 30-04-2015 16:30, Welton Vaz wrote:
> Amigos,
> Vcs já ouviram falar do teste de primalidade MillerRabin,
> http://goo.gl/oPQ5BE com ele vc consegui 2000 números primos em
> 5 segundos.
> Codigo aqui: http://pastebin.com/ZZvFyhqM

Olá!

Vejam meu código em [1], com 100.000 cliclos:

Encontrados 296317 números primos em 9.764606s!
Total de dígitos no último número: 7
Os primeiros 1.000 primos confere? True

Com 1.000 ciclos: Encontrados 4396 números primos em 0.041499s!

Será que eu errei em alguma coisa? Pelo menos os primeiros
1.000 primos estão corretos. :)

[1] https://gist.github.com/JuniorPolegato/c80e9dcc17f88fcffd51

--

[]'s

Junior Polegato

[Linux - Junior Polegato]

On 30-04-2015 17:52, Linux - Junior Polegato wrote:
> On 30-04-2015 16:30, Welton Vaz wrote:
>> Amigos,
>> Vcs já ouviram falar do teste de primalidade MillerRabin,
>> http://goo.gl/oPQ5BE com ele vc consegui 2000 números primos em
>> 5 segundos.
>> Codigo aqui: http://pastebin.com/ZZvFyhqM
>

> Vejam meu código em [1], com 100.000 cliclos:
> Encontrados 296317 números primos em 9.764606s!
> Total de dígitos no último número: 7
> Os primeiros 1.000 primos confere? True
> Com 1.000 ciclos: Encontrados 4396 números primos em 0.041499s!
> Será que eu errei em alguma coisa? Pelo menos os primeiros
> 1.000 primos estão corretos. :)
> [1] https://gist.github.com/JuniorPolegato/c80e9dcc17f88fcffd51

Atualizei o código para testar 10.000 primos e funcionou!
Impressionante! Parabéns!

--

[]'s

Junior Polegato

[Henr"Ikke" Pereira]

É. Tua implementação está funcionando bem. Acabei de bater com 100k ciclos e deu certo.

Mas não chega nem perto do sieve pra números grandes. Com 100k ciclos (296317 primos, último primo 4200023) leva 12.5s com esse algoritmo e 1.32s com o crivo (http://ideone.com/2PsvOa)

--

[]'s

Junior Polegato

--
--
------------------------------------
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ê está recebendo esta mensagem porque se inscreveu no grupo "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 obter mais opções, acesse https://groups.google.com/d/optout.

[Diego Rocha]

Daniel, qual foi a faixa que você testou?

Até 1.000.000 essa versão do crivo http://ideone.com/YTaMB roda em 0.6

[Bruno Becker]

Boa tarde a todos. Somente hoje entrei aqui pra olhar e vi duas coisas;

primeiro,realmente eu não descobri nada que alguem ja não tivesse descoberto... Eu juro que não sabia,descobri sozinho mesmo,mas enfim,vou retirar o video do youtube,e o tal registro em cartório esta nulo...

Outra coisa, gostei muito das melhorias do algoritmo,ficou show!!! Obrigado Junior Polegato.

Mas entre mortos e feridos sobrevivi com vantagens no fim de tudo,pois;

Apesar de ter pagado mico,aprendi novas coisas.

Isso serviu pra trazer a tona um novo tipo de algoritmo gerador de primos,que senão é o mais rapido,esta entre os mais,e poderá ser melhorado mais ainda(como todo programa).

E finalmente o principal pra mim, a parte matemática da coisa é verdadeira,e para meus estudos isso vai servir muito.

Pesso novamente desculpa a todos.

Não precisam(vcs sabem...) relacionar meu nome ao algoritmo e nada relacionado,a não ser lembrar deste mico,rsrsrs

é isso.

[Bruno Becker]

Boa tarde Junior!!!

Sou bem ruinzinho em programação,rsrsrs,teria como vc converter essa sua versão para Python 3? Ja tentei de tudo e só dá erro,rsrsrs

Valeu.

[Linux - Junior Polegato]

Olá!

Alterei o código em [1] para rodar tanto no Python 2 quanto no 3, e dei um otimizada tirando 2 e 3 dos primos iniciais para teste, contudo em meus testes deram que no Python 3 leva o dobro do tempo encontrado no Python 2.

[1] https://gist.github.com/JuniorPolegato/c80e9dcc17f88fcffd51

[]'s

Junior Polegato

--

[Bruno Becker]

Valeu cara!!! Ficou muito bom,testei aqui e ficou redondo,rsrs  Alterei ele para gerar um arquivo de texto com a lista de primos.

 Acho que não da pra otimizar mais o seu algoritmo,na minha opinião ja esta bastante rápido. Testei ele tanto em windows quanto em linux(ambos em python 3) e no linux teve 40% de ganho na velocidade.

Segue o link da alteração que fiz(não mexi em nada no seu algoritmo):

https://drive.google.com/file/d/0B-VoQj7RjQ9nUERQUlVFRmRsREk/view?usp=sharing

Novamente muitissimo obrigado.

[Bruno Becker]

ÚLTIMA VERSÃO(12/05/2015):

LINK:  https://drive.google.com/file/d/0B-VoQj7RjQ9nUERQUlVFRmRsREk/view?usp=sharing

[Linux - Junior Polegato]

On 12-05-2015 14:29, Bruno Becker wrote:
> Valeu cara!!! Ficou muito bom,testei aqui e ficou redondo,rsrs
> Alterei ele para gerar um arquivo de texto com a lista de primos.
> Acho que não da pra otimizar mais o seu algoritmo,na minha opinião ja
> esta bastante rápido. Testei ele tanto em windows quanto em
> linux(ambos em python 3) e no linux teve 40% de ganho na velocidade.
> Segue o link da alteração que fiz(não mexi em nada no seu algoritmo):
> https://drive.google.com/file/d/0B-VoQj7RjQ9nUERQUlVFRmRsREk/view?usp=sharing
> Novamente muitissimo obrigado.

Olá!

Na verdade tem sim como otimizar mais... Não sei como não
reparei isso antes, mas o limite_teste estava sendo um valor de ponto
flutuante, que por sua vez seria utilizado para fazer comparação com
inteiro, consumindo processamento desnecessário de ponto flutuante,
então o tornei um número inteiro, onde tive um ganho de 25% de
performance. Simplesmente faça:

limite_teste = int(lista[-1] ** 0.5)

[Bruno Becker]

Agora sim,ficou show. Melhorou bem mesmo esta alteração pra int. A questão é que ele gera .txt muito grande,e abrir normalmente é muito demorado(inviavel),uma solução que encontrei é usar o programa Editplus 3,abrir o txt com ele e salvar como html,ai fica bem levinho. Rodei um milhão de ciclos e gerou um .txt de 26 mb,e isso demorou no meu pc das casas bahia(celeron) 900 segundos no windows 7. Mas agora acho que chegou-se num algoritmo decente pra fatorar primos,valeu mesmo.

[Bruno Becker]

Só pro pessoal ter uma idéia da velocidade do alg:

Configuração do pc:

Intel Celeron 2.53GHz

2 GB ram

Windows 7

python 3

Tempo Calc: 0.125s

Total de Números Primos: 4396

Bom,é isso,se alguem conseguir algo(algoritmo) melhor que isso,estou aguardando ansiosamente,rsrsrs

Valeu!

[Henr"Ikke" Pereira]

http://ideone.com/09fOBy

0.02s e 6000 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 "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.

[Bruno Becker]

Boa noite Henrique.  Acho que tem muito a ver com a potencia da "maquina" tb,pois a minha é beemm fraquinha. Pra efeito de comparação,teste a versão do link a seguir,em Python 2,acho que vc vai conseguir um bom resultado:

https://drive.google.com/file/d/0B-VoQj7RjQ9nUkYyd2xtR2RYeE0/view?usp=sharing

teste 1430 ciclos,que vai dar 6000 primos.

Na minha maquina o resultado foi esse:

Tempo Calc: 0.0913491249084s
Total de Números Primos: 6067

Rodei num Celeron 2.53GHz,com 2GB ram,no Python 2 em Linux.

To curioso pra saber em quanto tempo sua maquina faz,rsrs

[Juan Lopes]

(Postando novamente. Acho que minhas mensagens não estão chegando para o grupo. Pelo menos não na web.)

Se é pra competir por tempo, melhor fazer em C++ com segmented sieves (esse sim imbatível em tempo).

http://ideone.com/haSEvj

2063689 primos em 0.092773s

[Bruno Becker]

Nem precisa fazer o teste, eu fiz aqui o teste o sieve,e realmente ele parece imbativel na velocidade,no meu pc ele é 4 vezes mais rápido que o "teorema becker". Mas ele ta dando erro para escrever em texto numeros grandes(o sieve),o erro é este:

Traceback (most recent call last):
  File "teste.py", line 25, in <module>
    arq.write (str((sieve(1000000000))))
  File "teste.py", line 7, in sieve
    b = [True]*m
MemoryError

Ou seja erro de memória para numeros muito grandes,que seria isso?

Em quarta-feira, 13 de maio de 2015 10:15:50 UTC-3, Henrique G.G. Pereira escreveu:

[Bruno Becker]

E o verdadeiro teste de um algoritmo deste tipo é com numeros grandes né,bom,com o "teorema becker" consegui este resultado:

Tempo Calc: 432.557624102s

Total de Números Primos: 2547620

Ultimo numero primo: 41999987

[Linux - Junior Polegato]

On 14-05-2015 08:40, Bruno Becker wrote:
> Nem precisa fazer o teste, eu fiz aqui o teste o sieve,e realmente ele
> parece imbativel na velocidade,no meu pc ele é 4 vezes mais rápido que
> o "teorema becker". Mas ele ta dando erro para escrever em texto
> numeros grandes(o sieve),o erro é este:
> Traceback (most recent call last):
> File "teste.py", line 25, in <module>
> arq.write (str((sieve(1000000000))))
> File "teste.py", line 7, in sieve
> b = [True]*m
> MemoryError
> Ou seja erro de memória para numeros muito grandes,que seria isso?

Olá!

Isso acontece pelo tamanho de memória necessária para alocar
esse vetor de bool, na prática, usa-se 32 bytes para a lista em si e
mais 4 para cada bool:

»» sys.getsizeof([])
32
»» sys.getsizeof([True])
36
»» sys.getsizeof([True] * 2)
40
»» sys.getsizeof([True] * 1000000)
4000032

Assim como você pediu para calcular 1 bilhão, teria que alocar
4GB para uma variável, o que não é possível para sistemas 32 bits, então
teria que usar um sistema 64 bits e ter uns 8GB de RAM para rodar, pois
vai precisar de espaço para os alocar os primos encontrados também. Em C
já esse vetor seria de 1GB pelo fato de que cada bool (char na verdade)
usar um byte. Esse vetor é usado, pelo que entendi do código, para
marcar quais números ímpares são divisíveis pelo número primo encontrado.

Realmente Sieve é imbatível computacionalmente na velocidade,
mas tem essas limitações, visto que o seu apenas guarda os primos
encontrados.

--

[]'s

Junior Polegato

[Linux - Junior Polegato]

On 14-05-2015 08:40, Bruno Becker wrote:

> Nem precisa fazer o teste, eu fiz aqui o teste o sieve,e realmente ele
> parece imbativel na velocidade,no meu pc ele é 4 vezes mais rápido que
> o "teorema becker". Mas ele ta dando erro para escrever em texto
> numeros grandes(o sieve),o erro é este:
> Traceback (most recent call last):
> File "teste.py", line 25, in <module>
> arq.write (str((sieve(1000000000))))
> File "teste.py", line 7, in sieve
> b = [True]*m
> MemoryError
> Ou seja erro de memória para numeros muito grandes,que seria isso?

Olá!

Deixei rodando aqui para chegar no número de 1 bilhão, quase 7
horas rodando:

Ciclos: 23809524
Último primo: 1000000033
Encontrados 50847538 números primos em 24428.056651s!
Total de dígitos no último número: 10
Os primeiros 10.000 primos confere? True

Memória utilizada: 250MB

--

[]'s

Junior Polegato

[Paul Eipper]

Rodando o código C++ da página na minha máquina:

"""
time ./segmented_sieve 1000000033 32768
50847538 primes found.

real 0m26.571s
user 0m22.086s
sys 0m0.100s

"""


E a implementação traduzida em python com os mesmos parâmetros:

"""
time python segmented_sieve.py
primes found: 50847538

real 8m25.162s
user 7m27.244s
sys 0m9.283s

"""



--
Paul Eipper

2015-05-14 17:53 GMT-03:00 Linux - Junior Polegato
<li...@juniorpolegato.com.br>:

> --
> --
> ------------------------------------
> 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ê está recebendo esta mensagem porque se inscreveu no grupo "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 obter mais opções, acesse https://groups.google.com/d/optout.

[Linux - Junior Polegato]

Olá!

Eu tinha feito sieve em C, esse processo de sieve não tem pra ninguém, mas fiquei curioso sobre esse segmented, tem como passar os códigos?

[]'s

Junior Polegato

[Paul Eipper]

Foi o que passei anteriormente:

http://primesieve.org/segmented_sieve.html

Python:

https://ideone.com/bLSQRg

Você recebeu essa mensagem porque está inscrito no grupo "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.

--

--
Paul Eipper

[Fabio C. Barrionuevo da Luz]

Bruno, https://docs.python.org/2/library/exceptions.html#exceptions.MemoryError

Fábio C. Barrionuevo da Luz
Acadêmico de Sistemas de Informação na Faculdade Católica do Tocantins - FACTO
Palmas - Tocantins - Brasil - América do Sul

http://pythonclub.com.br/

Blog colaborativo sobre Python e tecnologias Relacionadas, mantido totalmente no https://github.com/pythonclub/pythonclub.github.io .

Todos são livres para publicar. É só fazer fork, escrever sua postagem e mandar o pull-request. Leia mais sobre como publicar em README.md e contributing.md.

Regra básica de postagem:

"Você" acha interessante? É útil para "você"? Pode ser utilizado com Python ou é útil para quem usa Python? Está esperando o que? Publica logo, que estou louco para ler...

[Paul Eipper]

Se quiser reduzir o uso de memória, existe o segmented sieve, que
adaptei diretamente de [1]:

https://ideone.com/bLSQRg
Success time: 0.03
primes found: 10000


[1] http://primesieve.org/segmented_sieve.html

--
Paul Eipper

2015-05-14 10:23 GMT-03:00 Linux - Junior Polegato
<li...@juniorpolegato.com.br>:

> --
> --
> ------------------------------------
> 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ê está recebendo esta mensagem porque se inscreveu no grupo "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 obter mais opções, acesse https://groups.google.com/d/optout.

[Juan Lopes]

Se é pra competir por tempo, melhor fazer em C++ com segmented sieves (esse sim imbatível em tempo).

http://ideone.com/haSEvj

2063689 primos em 0.092773s

https://github.com/juanplopes

[Bruno Becker]

Pois é,to impressionado, mais de 2 milhões de primos neste tempo é pra desanimar o "meu" algoritmo mesmo,rsrs Só tenho uma duvida em relação ao sieve,seria possivel ele fatorar apenas um numero gigantesco fornecido a ele,tipo um numero com 20 milhôes de digitos,ele faria isso,ou ele só funciona de forma linear,tipo começando do "zero"? Pq to com umas idéias de implementar isso no "teorema becker",tipo entro com um numero gigantesco multiplo de 42,somado a chave,e vejo no que dá...rsrsrs Pois ele só iria calcular um ciclo (chave com 12 numeros gigantescos),não demoraria tanto quanto se fizesse isso de forma linear,acho eu,rsrsrs

[Bruno Becker]

Ja tinha pesquisado sobre comparações de velocidade das linguagens,e infelizmente no que o Python ganha em facilidade de implementação ele perde em velocidade,por exemplo vi que a linguagem C é até 600x mais rápida que Python para calculos,a questão é que fazer certas coisas que são feitas facilmente em Python na linguagem C é bem complicado....

No que diz respeito a velocidade pra gerar primos o "teorema becker" é realmente uma carroça,apesar da extrema melhorada que o Junior Polegato fez no alg,acho que o "teorema becker" serve mais como uma "observação matemática",ou outra forma "divertida" de gerar primos,rsrsrs

[Juan Lopes]

Se você conseguir fatorar um número gigantesco (e.g. com 20 milhões de dígitos) durante o tempo das nossas vidas, você estará rico e famoso instantaneamente, pois isso significa que você consegue quebrar RSA, que se baseia justamente nisso.

[Bruno Becker]

7 horas,rsrsrs Ele é demorado,mas creio que gera todos primos com exatidão,e o melhor exige muito pouco de hardware. Mas ta legal brincar com este algoritmo,e sempre fica aquela questão "Será que dá pra melhorar?",rsrsrs

Valeu!

[Bruno Becker]

kkkkkkkkkk sei que fiz uma pergunta ridicula,rsrsrs  Mas como sei muito pouco de programação,pensei ("vai que ele sabe o pulo do gato...,vou perguntar,rsrs).

Mas valeu pela paciência,rsrs

[Bruno Becker]

Oi Junior, fiz uma brincadeira com uma versão antiga do "teorema",do tipo multiplicar um numero por 42 e somar a chave,pra depois fatorar,olha o resultado em python 3 no windows:

cycle(b) 1-[6693013185151, 6693013185163]

cycle(b) 2-[6693013185191, 6693013185193, 6693013185197]


Time calc: 5.569210052490234s
The program began to roll 14h54
and ended the 14h54

Melhor né? Aliás vou seguir neste sentido agora,pois este algoritmo nem é otimizado e ja deu este resultado,imagina se melhora-lo...

Mas é claro,pra numeros grandes tem que usar 1 ou 2 ciclos no máximo...

[Linux - Junior Polegato]

On 15-05-2015 12:02, Bruno Becker wrote:
> Oi Junior, fiz uma brincadeira com uma versão antiga do "teorema",do
> tipo multiplicar um numero por 42 e somar a chave,pra depois
> fatorar,olha o resultado em python 3 no windows:
> cycle(b) 1-[6693013185151, 6693013185163]
> cycle(b) 2-[6693013185191, 6693013185193, 6693013185197]
> Time calc: 5.569210052490234s
> The program began to roll 14h54
> and ended the 14h54
> Melhor né? Aliás vou seguir neste sentido agora,pois este algoritmo
> nem é otimizado e ja deu este resultado,imagina se melhora-lo...
> Mas é claro,pra numeros grandes tem que usar 1 ou 2 ciclos no máximo...

Olá!

Não entendi muito bem, pois para fatorar um número, você
deveria conhecer todos os primos até a raiz quadrada desse número.
Depois disso ir dividindo esse número pelo primeiro primo, pegar o
resultado e dividir novamente, e assim por diante, de bate pronta:

def fatorar(numero):
primos = list(segmented_sieve(numero)) # ou becker(numero) ou
sieve(numero)
def _fatorar(num):
if num in primos:
return num, 1
for p in primos:
if num % p == 0:
return p, num / p

fatorado = {} # primo: potencia
while numero > 1:
primo, numero = _fatorar(numero)
if primo in fatorado:
fatorado[primo] += 1
else:
fatorado[primo] = 1

resultado = ''
for primo, potencia in sorted(fatorado.items()):
resultado += ' * %i' % primo
if potencia > 1:
resultado += ' ^ %i' % potencia

return resultado[3:]



---------------- Saída --------------
Número a fatorar: 1000000
1000000 = 2 ^ 6 * 5 ^ 6


--

[]'s

Junior Polegato

[Bruno Becker]

È isso mesmo,a unica diferença é que pra fatorar direto um numero primo grande,de duas uma,ou vc cria um banco de dados com todos primos pra acessar(o que não é o caso),ou vai no velho esquema de fatorar pelos impares,por isso que usei um algoritmo antigo(que não usava os primos gerados para fatorar,mas usava os impares).
To mexendo aqui pra deixar o algoritmo apresentavel,mas creio que será um novo metodo de lidar com o algoritmo... Vamos ver,rsrsrs

coloquei 9999999999999*42+ a chave completa.
ai ele pegou apenas uma chave e um ciclo,e fatorou pelos impares e tals....
dois numeros primos de 15 digitos rapidinho,rsrs

Sem ter que fatorar todos anteriores,indo direto ao ponto.

CICLO(C) 1-[419999999999977, 419999999999989]

Tempo Calc: 18.298831939697266s
Total de Números Primos: 2

[Bruno Becker]

Boa noite a todos!

Estou de volta,rsrs,andei trabalhando no "teorema" esse tempo todo,consegui descobrir coisas novas,e tente programar tais coisas pra efeito de teste,mas a verdade é que realmente sou ruim em programação,kkkkk

Sendo assim vou colocar aqui a "teorema" que acredito estar completo agora,e quem quiser transformar em programa,ficarei grato.

Vamos lá:

C = [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]

PP= C+x*42

NP=C*C

P= Se PP diferente de NP em lista contendo TODOS C e todos C*C até P,eliminando pelo mesmo metodo os P anteriores.

Legenda:

PP=Possivel Primo
NP=Nunca Primo,sendo todos NP divisiveis por primos >11 ou 5.
P=Primos.


Ou seja,dentro de C,temos 2 tipos de numeros,NP e P,se multiplicarmos TODOS C entre si,temos todos NP,e o que for diferente disto é primo,exemplo:

C = [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]+42: [43, 47, 53, 55,59, 61, 65, 67, 71,73, 79, 83]+42:[85,89, 95, 97, 101, 103, 107, 109, 113, 115, 121, 125]



olhando as chaves acima,podemos começar por 5*5=25,ou seja eliminamos o 5 e o 25,e todos numeros até 25 são primos.

E assim por diante...

Não tem segredo,é matematica simples.

Ou seja,isto é um crivo,que só precisamos usar multiplicação(C*C),e comparação com PP,pra ver se é P.

Imagino que será um crivo bem rapido,por não usar divisão.

Mas volto a frisar,tem que multiplicar TODOS C por C,ou seja,quanto maior o numero,mais numero serão multiplicados,por exemplo,se for o numero 28561,temos que multiplicar todos C entre si anteriores a ele para comparação.

Qualquer duvida só perguntar,mas só responderei amanhã,pois ja mexi muito com isso hoje,rsrsrs,por isso joguei a toalha no quisito programação,kkkkk

Valeu!!!

Em quarta-feira, 29 de abril de 2015 16:12:18 UTC-3, Bruno Becker escreveu:

[Ivan Ogasawara]

Oi Bruno! Ja tentou usar o numpy?

Grande abraço!

--

--
------------------------------------
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 "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.

[Bruno Becker]

Ja li a respeito desta possibilidade,mas não entendi muito bem.

Eu consegui multiplicar todos por todos,mas apenas dentro de um looping(ciclo c),gostaria de armazenar todos gerados pela multiplicação e multiplica-los pelo proximo ciclo,assim por diante,ai é que eu não consegui,rsrs

Valeu.

[Bruno Becker]

Corrigindo,onde eu escrevi:" P= Se PP diferente de NP em lista contendo TODOS C e todos C*C até P,eliminando pelo mesmo metodo os P anteriores.", Esta errado,a lista deve conter apenas os multiplos,ou seja C*C,pois os que não forem multiplos são P(primos).

[Bruno Becker]

Andei pesquisando novos metodos de encontrar primos,e encontrei o teorema de fermat,pesquisei e montei um programa colando códigos,e corrigindo para gerar primos a começar de um numero impar qualquer,independente do numero de algarismos,ficou bem rapido e objetivo,mas faltam testes,sabendo que o teorema de fermat gera erros(muito pequenos). Esse que fiz gera primos baseado em impares,somando +2. A questão é,alguem poderia me ajudar a juntar o "teorema becker" com este programinha de fermat?

Segue o link do gerador de primos de fermat: https://drive.google.com/file/d/0B-VoQj7RjQ9nMVJXbUw2QjNGMkk/view?usp=sharing

segue o código do mesmo:

import math
print("PRIMOS DE FERMAT ")
arq = open("Primos_Fermat.txt", "w")

print("\n")

a = int(input("Digite um numero IMPAR inicial: "))

     


ciclo = int(input("Digite o numero de ciclos: "))

contador = 0



import time
t0=time.time()
hora_start=time.localtime()[3]
minuto_start=time.localtime()[4]


while ciclo > contador:

      def isPrime(p):
          if(p==2): return True
          if(not(p&1)): return False
          return pow(2,p-1,p)==1
    


      if isPrime(a)== True:
         primo = a
  
        
        
         arq.write("[")
         arq.write (str(primo))
         arq.write("]")
        

      else:
           False
      a = a+2
          
      contador = contador+1
     
tf=time.time()
arq.write("\n")
print("\n")
print("TERMINADO!")
print("\n")
print ("Tempo Calculo: ",tf-t0,"[s]")
print ("\n")
print ("Total digitos ultimo numero: ")
print (len(str(primo)))
print("Ultimo numero: ",primo)
print("\n")

arq.write("\n")
arq.write ("Tempo calculo: ")
arq.write (str(tf-t0))
arq.write ("s")
arq.write("\n")
hora_end=time.localtime()[3]
minuto_end=time.localtime()[4]
arq.write (str('O programa iniciou as: '))
arq.write (str(hora_start))
arq.write (str('h'))
arq.write (str(minuto_start))
arq.write("\n")
arq.write (str('E terminou as: '))
arq.write (str(hora_end))
arq.write (str('h'))
arq.write (str(minuto_end))
print ('O programa iniciou as: ',hora_start,'h',minuto_start)
print ('E terminou as: ',hora_end,'h',minuto_end)
arq.close()
print ("\n")

input("Tecle ENTER para sair")

exit

 
#Se alguem conseguir juntar o teorema becker com o de fermat acho que vai ficar legal,basta adicionar a variavel "a" do programa de fermat a chave base do teorema becker,e creio que vai dar certo.

[Sinval Júnior]

Bruno, coloque seus códigos no https://gist.github.com é mais prático para compartilhar em grupos

--

[Marcelo Andrade]

2015-05-15 8:58 GMT-03:00 Bruno Becker <bbecke...@gmail.com>:
> 7 horas,rsrsrs Ele é demorado,mas creio que gera todos primos com exatidão,e
> o melhor exige muito pouco de hardware.

Desculpem-me se não acompanhei tudo, mas achei importante pontuar
já que não vi ninguem comentar aqui. Bruno, como você diz que não é
da área de computação, para o estudo de algoritmos deve-se levar em
consideração apenas suas complexidades e não necessariamente só
seus tempos de execução.

Assim, se eliminam questões relativas a capacidades de hardware e se
pode afirmar melhor se um algoritmo será eficiente hoje ou daqui a cem
anos.

https://www.google.com.br/search?q=complexidade+de+algoritmos

Atenciosamente.

--
MARCELO F ANDRADE | Belem, Amazonia, Brazil | http://about.me/mfandrade

[Bruno Becker]

Sim,vc tem toda razão,na verdade a dita rapidez eu nem me importo tanto,mas um algoritmo só é "valorizado" se é rapido,principalmente na busca por numeros primos...
Na verdade este "teorema",que ainda podemos chamar de hipotese,ja foi provado nos primeiros algoritmos feitos neste tópico com a ajuda de todos aqui,e isso é oque realmente importa para mim,a prova de que ta hipotese é verdadeira...

Tenho muito que mostrar sobre tal hipotese,coisas que provavelmente daria uma grande discussão filosofica,do tipo (isso não pode ser por acaso...)...

Fiz um pdf em ingles(traduzido pelo google,rsrs),faz um tempo,o qual mostra que cheguei nisso tudo descobrindo que em uma progressão aritmética simples,do tipo n+2,há uma proporção de 21 numeros(metade de 42...),que chamo de ciclo base,e a area delimitada de aparecimento dos primos obedece um padrão booleano fixo:
x0x00xx0xx0xx0xx00x0x,sendo x = pode ser primo, e 0 = nunca é primo.

Há muitas outras coisas interessantes nisso,que em breve mostrarei,ainda não sei se em formato de texto ou video...

Mas pra que tiver curiosidade segue o pdf:

https://drive.google.com/file/d/0B-VoQj7RjQ9neTdOcmdXU2xmbWc/view?usp=sharing

[Ivan lopes]

Estou acompanhando .... quando eu tinha 16 anos por meio de combinação e papel picotado cheguei as formulas de probabilidade mas com outros nomes ... na época achei que fosse genio, mas na minha inocência eu apenas havia descoberto um fato, as verdades matemáticas estão na natureza e no dia a dia .... arranhar elas eh apenas um vislumbre da realidade. Todavia isso me motivou a estudar engenharia e matemática .... mas infelizmente não consegui arranhar mais nada :-)

--

[Bruno Becker]

Boa tarde Ivan!

Eu considero uma forma de genialidade "descobrir" algo que alguem ja tenha descoberto,o qual se ignorava...

Considero que eu esteja no caminho correto,ainda depois de recentemente ter lido o livro " A musica dos numeros primos" do Marcus du sautoy,o qual fala sobre todas descobertas relacionadas aos primos,e foi minha surpresa quando li o titulo de um dos capitulos "42 – a resposta para a grande pergunta",ai pensei " só falta falar sobre "minha teoria",rsrsrs,mas não,o capitulos fala sobre outra descoberta que relaciona os primos ao numero 42.Ou seja,estou realmente no caminho certo...

Neste mesmo livro me identifiquei um pouco com a historia de Ramanujan,um funcionario publico indiano,que tinha por hobby a busca pelo mistério dos primos,sem ter formação academica,e descobriu varias coisas que ja tinha descoberto,mas sozinho,e por fim acabou contribuindo com sua criatividade e ajuda de matematicos academicos,ao mundo matematico.

Enfim,esta busca é uma das poucas coisas que realmente gosto de fazer,minha verdadeira vontade,apesar de acreditar que não há uma ordem nos numeros primos,eles na minha opnião são o caos quantico por detrás da ordem,aliás,no mesmo livro tambem há fortes indicios da relação do comportamento quantico das subparticulas e os primos,enfim,algo fascinante.

[Ivan lopes]

A teoria não eh sua ... mas pode um dia ser sua e de todos ... oq quero dizer eh que a ciência existe e o trabalho do cientista eh arranhar essa janela e ver um pedacinho. Ninguém faz ciência pensando em criar uma lei ou teoria ... estuda-se um assunto e com profundidade pode se chegar numa afirmação. O método cientifico eh o mecanismo da ciência que corrige os erros humanos.  Quanto a ser gênio ... isso não existe, na verdade tenho algumas exceções como o mestre Elon Lages :-)  ... de resto eh esforço combinado, pois ciência eh a soma do pensamento de ontem com os de hoje. Se até Newton errou ... 

Ps: Não faco critica a você.

[Paul Eipper]

Offtopic, mas se quiser explorar os primos relacionados à física,
existe relação entre simetrias de grupos e String Theory (teoria das
cordas) que definem objetos fundamentais. Se quiser perder um (longo)
tempo na wikipedia e youtube (tudo em ingles):

https://en.wikipedia.org/wiki/Supersingular_prime_%28moonshine_theory%29
https://en.wikipedia.org/wiki/Monster_group
https://en.wikipedia.org/wiki/Monstrous_moonshine

Monster Group - Numberphile (com John Conway):
https://www.youtube.com/watch?v=jsSeoGpiWsw

https://www.quantamagazine.org/20150312-mathematicians-chase-moonshines-shadow/

--
Paul Eipper

[Paul Eipper]

PS: Ah, e nessa historia Ramanujan aparece como um personagem central
;) (ver Umbral Moonshine, ultimo link)


--
Paul Eipper

[Bruno Becker]

Valeu pelo material Paul! Meu inglês é básico,mas nada que um google tradutor não resolva,rsrs

Estas relações entre matemática e a "realidade" é o que me atrai nisso tudo,é tipo buscar entender o código da Matrix da realidade,o que os antigos judeus chamavam de cabala...

[Bruno Becker]

Parece que ninguem mais ta interessado nisso...rsrs Mas acho que encontrei algo que possa acelerar um pouco mais o alg do teorema,segue a novidade:

" Um divisor pode ser eliminado da lista sempre após seu quadrado,por exemplo:

11*11 = 121,após 121 o numero 11 pode ser eliminado da lista de divisores,pois todo numero acima de 121 será dividido por um numero maior que 11,na chave do teorema.

O proximo primo é o 13,o quadrado de 13 é 169,ou seja,após 169 eliminamos o 13 da lista de divisores, e assim por diante".

Valeu!

[Alex]

Eu descobri algo que pode melhorar ainda mais seus resultados.

Faz seu programa em C!

Python é uma linguagem interpretada e como tal é bem mais lenta que C.

Todo código complexo em Python está escrito em C e modularizado como uma extensão.

http://theunixgeek.blogspot.com.br/2008/09/c-vs-python-speed.html

[Bruno Becker]

Bom dia!

Elaborei um novo algoritmo para o "teorema becker",o qual é um crivo,que não usa divisão,apenas multiplicação e comparação.

Tenho certeza que o mesmo gera primos de forma precisa.

Tentei implementar tal algoritmo em Python,mas pela minha falta de experiencia em programação ele ficou muito complexo,e por consequencia lento...

Sendo que o algoritmo é simples,tenho certeza que alguem com experiencia o fará com as "mãos nas costas",e de forma eficiente.

Abaixo segue o algoritmo resumido,com referencias pythonicas:

-------------------------------------------------------------------------------

1-  base= [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]

2-  gerar base +42 a cada ciclo

3-  lista1 = lista1.append(base)

4-  lista1.remove(1)

5- mult= multiplicar x for x in lista1,se mult > lista1[-1] break.

6-  lista2=lista2.append(base) #nesta lista se mantem o numero 1

7-  base2= zip(mult+lista2)

8-  primos= remover TODOS IGUAIS de base2,oque for UNICO é numero primo.

----------------------------------------------------------------------------------------------------------------------

Então é isso,pelo menos é um NOVO algoritmo para gerar numeros primos,e essa lógica acima pode ser aplicada a qualquer outra linguagem.

Qualquer duvida ou crítica,estou sempre olhando aqui.

Valeu!

[Juan Lopes]

Só uma observação: o crivo de Eratóstenes não usa divisão também.

--

--
------------------------------------
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 "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

[Bruno Becker]

Sim,a lógica é quase a mesma,por isso mesmo creio q é o melhor caminho para melhorar o "teorema becker",depois q percebi q os não primos gerados pela chave são todos multiplos dos numeros da chave,isso penso eu elimina muitoooos outros numeros no processamento.

[Bruno Bkr]

Boa tarde!

Segue um documento em pdf,com toda teoria matemática do "teorema",e novas "descobertas",como sei que muitos aqui tem interesse nesta area em especifico,creio ser um ótimo lugar para avaliarem isso:

Creio ter "descoberto" a razão da aparente desordem nos números primos, no fim do documento explico isso, creio ter a ver com algo que chamo de "cruzamento de p.a",onde cada número dos ciclos gera uma p.a de seus múltiplos,as quais se concentram em certos pontos,diminuindo a aparecimento de números primos.

Enfim,estou aberto a criticas,e no próprio documento,falo sobre uma das criticas que recebi aqui,e que me ajudou muito a amadurecer a teoria em si.

Link do pdf:

https://drive.google.com/file/d/0B1gZv4JoPpFlNVhBWGs0VURxZ1E/view?usp=sharing

obs; Fiquem a vontade para gerar programas para testar essa teoria,será um prazer.

[Bruno Bkr]

pdf corrigido:

https://drive.google.com/file/d/0B1gZv4JoPpFla09Td2JaZ2ZrS1k/view?usp=sharing

[Pedro Werneck]

Bruno,

Não, aqui não é um lugar ótimo para isso pois é uma lista de Python.
Citando o que eu já disse em abril, peço que leve a discussão sobre a
sua teoria
para uma lista sobre Matemática e aqui foque apenas no seu código Python.

> --
> --
> ------------------------------------
> 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 "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.



--

---
Pedro Werneck

[Alexandre Fioravante de Siqueira]

Bruno, tudo certo?

Cara, vou te dar uma dica. Escreva suas ideias (em inglês) sobre o seu tema e submeta no http://www.arxiv.org/.

Depois divulgue em comunidades matemáticas. Acredito que poderia ser de maior valia pra você.

Quanto à parte do código, aí sim acredito que os brothers podem te ajudar :)

Abraços.

Alexandre Jaguar

[Sinval Júnior]

Bruno, já ouviu falar em Scipy[1] neste projeto existe umas 8 implementações para cálculos de números primos com performance surpreendente[2]. Acredito que nestas [3] listas de discussões você irá encontrar pessoas que podem discutir mais sobre este assunto.

1 - http://scipy.org/scipylib/mailing-lists.html

2 - http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n

3 - http://scipy.org/scipylib/mailing-lists.html#mailing-lists

1 - http://scipy.org/

Ao encaminhar esta mensagem, por favor:
1 - Apague meu endereço eletrônico;
2 - Encaminhe como Cópia Oculta (Cco ou BCc) aos seus destinatários. Dificulte assim a disseminação de vírus, spams e banners.

#=================================================================+
#!/usr/bin/env python
nome = 'Sinval Júnior'
email = 'sinvalju arroba gmail ponto com'
print nome
print email
#==================================================================+

Você está recebendo esta mensagem porque se inscreveu no grupo "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 obter mais opções, acesse https://groups.google.com/d/optout.

[Bruno Bkr]

Pedro Werneck

30 de abr

Re: [python-brasil] Re: Teorema Becker - Gerador Numeros Primos em Python 3

Bruno, 

Pedro Werneck  30 abril:

"OK, agora sua intenção ficou mais clara. Eu estudo simbolismo e 
religiões comparadas, e se você chegou a essa conclusão sobre 
primalidade a partir do número 42 por guematria ou outro método ou 
hermenêutica puramente simbólico e não-matemático -- que não é o que 
você mostrou aqui -- eu até me interesso em ver os detalhes, mas por 
favor, em texto, não em vídeo. "

[Pedro Werneck]

Bruno,

Não precisa economizar caracteres. Pode citar a mensagem inteira.

"OK, agora sua intenção ficou mais clara. Eu estudo simbolismo e

religiões comparadas, e se você chegou a essa conclusão sobre
primalidade a partir do número 42 por guematria ou outro método ou
hermenêutica puramente simbólico e não-matemático -- que não é o que
você mostrou aqui -- eu até me interesso em ver os detalhes, mas por
favor, em texto, não em vídeo.

Se você queria provar que sua descoberta é válida matematicamente
através do código, já está claro que isso não é necessário, pois a
própria prova matemática é trivial. Sua atitude em apresentar algo
trivial como teorema matemático e como uma descoberta revolucionária
depõe contra você, pois você mesmo tinha obrigação de saber isso
antes. Tome como exemplo o maior gênio do simbolismo no século XX,
René Guénon, que era um matemático brilhante antes de ingressar nos
movimentos ocultistas da França e nos estudos doutrinais.

Não vou te remover da lista ou excluir suas postagens porque você
reconheceu o erro na sua atitude e explicou melhor suas intenções, mas
aqui realmente não é o lugar para isso. Se alguém quiser ajudar a
melhorar o código, fique à vontade."

Vou assumir que você me citou fora de contexto por distração, não por desonestidade. Se você tiver dúvidas sobre seu código Python, fique à vontade para discutí-las na lista, mas aqui não é o lugar mais adequado para discussões sobre o seu "teorema".

[Bruno Bkr]

No programa abaixo,to gerando duas listas, uma pa com termo fixo(1), e outra pa2 com TODOS os valores da lista pa,mas o valor de pa2 não esta percorrendo todos de pa(1),por exemplo,com 1 ciclo ele usa apenas o ultimo valor da lista,e assim por diante...

Alguem me ajuda?

segue o link do "programa": https://drive.google.com/file/d/0B1gZv4JoPpFlQUtGZVdfa1BiYjg/view?usp=sharing

o código:

termo = 1

ciclo = int(input("Digite o numero de ciclos da pa: "))

contador = 0

contador2 = 0

x = termo

y = termo

pa=[]

pa2=[]

while ciclo > contador:

      v = [4, 6, 2, 4, 2, 4, 2, 4, 2, 6, 4, 2] 

      tam_v = len(v) 

      elementos = ciclo * tam_v 

      pa = [x + y * v[0]] 

      for n in range(1, elementos): 

               pa.append(pa[-1] + y * v[n % tam_v])

               contador = contador+1

while ciclo > contador2:

     for x in sorted(pa):

          termo2 = x

          a = termo2

          b = termo2

       

          v = [4, 6, 2, 4, 2, 4, 2, 4, 2, 6, 4, 2] 

          tam_v = len(v) 

          elementos = ciclo * tam_v 

          pa2 = [a + b * v[0]] 

          for n in range(1, elementos): 

                   pa2.append(pa2[-1] + b * v[n % tam_v])

               

                   contador2 = contador2+1

print(pa2)

[Bruno Bkr]

Baseado na geração de números primos pela pa de phi(42) fiz o programa abaixo, o qual confimou gerar primos sem erros,mas ficou muitooooo lento. Alguem teria ideias de como deixar isso mais rapido. mais que 100 ciclos o negocio enche a memória do pc e trava tudo,kkkk

https://gist.github.com/bbeckercontato/b851567e87e307931c52

https://gist.github.com/bbeckercontato/b851567e87e307931c52

[Bruno Bkr]

Melhorei muito,ja esta bem rápido:

Digite o numero de ciclos da pa: 370000
('Foram encontrados ', 1003321, ' numeros primos')

('ultimo numero primo: ', 15540001)

('Tempo de executado: ', 27.753000020980835)

('Os primeiros 10.000 primos confere?', True)
tecle alguma tecla para sair

Se alguém quiser ajudar a melhorar mais ainda,serei grato:

https://gist.github.com/bbeckercontato/357049a250f411abdad9#file-primos_phi42-py

[Bruno Bkr]

Versão mais rápida(graças ajuda do Juan):

https://gist.github.com/bbeckercontato/8d3fa3dfd91438455291#file-phi42_primos-py

[Bruno Bkr]

Versão corrigida e que gera lista em html(pois carrega listas grandes melhor que txt):

https://gist.github.com/bbeckercontato/7e2b42fbc7e8f736c1d2#file-geraprimos42-py

[Bruno Bkr]

https://gist.github.com/bbeckercontato/21d7688e6168a873da62#file-primosphi42-py

Digite o numero de ciclos da pa: 2000000

('Foram encontrados: ', 4889139, ' numeros primos')

('Ultimo numero primo: ', 83999999)

('Tempo executado: ', 83.48659110069275)

('Os primeiros 10.000 primos confere?', True)

[Bruno Bkr]

Bom dia pessoal,o programa evoluiu um mais um pouco,acho que ja esta bem rápido:

https://gist.github.com/bbeckercontato/9c05b967699838306531#file-geraprimos-py


https://www.facebook.com/groups/python.brasil/permalink/776151709156368/


Em Cpython:

user@user:~$ python geraprimos.py
Digite limite: 100000100
100000049


('Tempo executado: ', 97.1843409538269)


Em pypy:

user@user:~$ pypy geraprimos.py
Digite limite: 100000100
100000049


('Tempo executado: ', 23.566112995147705)

[Erico GR]

legal,

com pypy, na minha máquina, executou bem rápido:

$ pypy geraprimos.py

Digite limite: 500000000

('Tempo executado: ', 55.12839198112488)

Foi gerado lista em arquivo de texto no local do programa

[Bruno Bkr]

Legal heim,é varia de maquina pra maquina,imagino que agora sim posso dizer pelo menos que em Python este algoritmo é um dos mais rápidos do mundo para gerar números primos. O unico problema é que aloca muita memória e trava,resolvido este problema ai sim vai ficar perfeito. Não sei programar em C,mas creio que se alguem fizer este mesmo algoritmo em C vai ficar muitoooo rápido. Que bom que gostou,espero melhorar ainda mais este alg. Valeu.

[Pedro Werneck]

2016-02-22 16:18 GMT-03:00 Bruno Bkr <bbecker...@gmail.com>:
> Legal heim,é varia de maquina pra maquina,imagino que agora sim posso dizer
> pelo menos que em Python este algoritmo é um dos mais rápidos do mundo para
> gerar números primos.

Acho que ainda está longe disso.

https://gist.github.com/pjwerneck/044577f0347045a8d4e3

$ python primos.py
Digite limite: 100000100

('Tempo executado: ', 6.4174699783325195)


E o seu código na mesma máquina:

$ python geraprimos.py
Digite limite: 100000100

('Tempo executado: ', 93.21370005607605)

[Rodrigo Baron]

Bruno,

parabéns pelo seu trabalho e você deve saber que a existência de uma teoria igual a sua não desmerece seu trabalho... Se você quer construir o algoritmo mais rápido do mundo para gerar números primos você precisa antes de tudo provar matematicamente que seu algoritmo sempre vai gerar um numero primo. Em seguida você deve provar <de alguma forma> que seu algoritmo é o mais rápido independente de tecnologia.

Como você já disse não ser matemático e nem programador aconselho a estudar Mathematical Proofs (Demostrações Matemáticas) para conseguir provar a sua teoria (e consequentemente desenvolver a sua mentalidade de dedução), e também estudar algoritmos para conseguir avaliar[1] melhor o seu algoritmo.

Sobre C e Python, se você desenvolver o seu algoritmo em C não significa que seu algoritmo vai ser mais rápido, e sim a implementação do algoritmo.. Matemáticos gostam de Python porque conseguem se expressar muito bem com ele (como este artigo de Jeremy[2]).

[1] http://pt.stackoverflow.com/questions/56836/defini%C3%A7%C3%A3o-da-nota%C3%A7%C3%A3o-big-o/56868#56868

[2] http://jeremykun.com/2014/05/26/learning-to-love-complex-numbers/

Att,

[Bruno Bkr]

Valeu pelo apoio, vou tentando né, toda teoria leva anos, senão decadas para ser efetivada, então vou aprimorando com o tempo. Muito obrigado.

--

--
------------------------------------
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 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/E2vDoLkgAt0/unsubscribe.
Para cancelar inscrição nesse grupo e todos os seus tópicos, envie um e-mail para python-brasi...@googlegroups.com.

[Pedro Werneck]

Bruno,

Estou com a impressão de que você não tem nenhum parâmetro de
comparação para seu algoritmo e sua implementação, e por isso está
superestimando sua eficiência baseando-se no valor simbólico. Seu
algoritmo é apenas um crivo, e como outros crivos tem duas partes: a
seleção dos candidatos, e a exclusão dos números compostos. O problema
é que tanto seu método de exclusão quanto a fatorização que você usa
para seleção são muito complicados para implementar eficientemente, e
para primos pequenos acabam perdendo para uma implementação eficiente
mas burra que simplesmente assume que todos os inteiros são primos e
exclui todos os múltiplos de primos menores que sqrt(n). Para primos
grandes, testes de primalidade são mais eficientes de qualquer forma.

Para te ajudar resolvi escrever esse script que tem algumas
implementações bem mais rápidas de geradores de primos em Python puro,
e algumas variações que fiz do seu algoritmo para ilustrar o que estou
dizendo.

https://gist.github.com/pjwerneck/f3a045ed7ac50335dbe7


Aqui vai a saída para os primos até 10e6:

becker
+ set([])
- set([999979, 999983])
--------------------------- --------- -------- ----
rwh_primes2 0.0320568 1
rwh_primes1 0.0416548 1.29941
rwh_primes 0.0448561 1.39927
sieve_wheel_30 0.0480661 1.49941
sieveOfEratosthenes 0.0518439 1.61725
becker_slices_rwh_exclusion 0.055841 1.74194
ambi_sieve_plain 0.122804 3.83082
sieveOfAtkin 0.183953 5.73835
sundaram3 0.196427 6.12746
becker_simple 0.352265 10.9888
simple_mod_6 0.482143 15.0403
becker_opt 0.489479 15.2691
becker 0.508519 15.8631 ERRO
--------------------------- --------- -------- ----

E aqui até 10e7:


becker
+ set([])
- set([9999991])
--------------------------- -------- -------- ----
rwh_primes2 0.358201 1
rwh_primes1 0.480661 1.34188
rwh_primes 0.502626 1.4032
sieve_wheel_30 0.553432 1.54503
sieveOfEratosthenes 0.575705 1.60721
becker_slices_rwh_exclusion 0.631324 1.76249
ambi_sieve_plain 1.52701 4.26301
sieveOfAtkin 1.90058 5.30591
sundaram3 2.82858 7.89662
becker_simple 5.40449 15.0879
becker_opt 6.02444 16.8186
becker 6.09869 17.0259 ERRO
simple_mod_6 6.31995 17.6436
--------------------------- -------- -------- ----

A primeira coluna é o nome da função, a segunda o tempo de execução, e
a terceira o tempo proporcional à implementação mais rápida.

Como foi dito anteriormente nesse tópico, seu algoritmo é apenas uma
maneira bem complicada de dizer que todo primo tem a forma 6k±1, então
simple_mod_6 é uma implementação burra que fiz usando apenas isso para
determinar os candidatos, como pior caso. Como você pode ver, roda em
um tempo bem próximo do seu.

Sua implementação (becker) tem um erro e não gera todos os primos até
o limite. Eu corrigi isso e fiz algumas melhorias no seu código, em
becker_opt, mas ainda está bem próximo.

Em becker_simple eu fiz uma implementação mais simples e eficiente do
seu método de fatorização para selecionar os candidatos, e usei o
mesmo método de exclusão do simple_mod_6. Tem uma melhora, porque
diminui um pouco a população, mas nada muito substancial.

Em becker_slices_rwh_exclusion eu fiz uma implementação do seu método
de seleção usando extended slices e usei o código de exclusão do
rwh_primes. Ficou 10x mais rápido do que sua implementação original,
mas comparado com o rwh_primes -- que assume todos os números como
candidatos -- seu algoritmo ainda leva mais tempo, o que significa que
a redução da população pelo seu método de fatorização não é o
suficiente para compensar a complexidade adicional.

Todas essas implementações terão problemas com memória para gerar
primos realmente grandes.

Resumindo, a complexidade asintótica do seu algoritmo é a mesma de
outros crivos, mas a complexidade da álgebra que você usa para seleção
e principalmente para a exclusão torna a implementação bem mais lenta
do que uma implementação mais burra porém mais eficiente.

> Você recebeu essa mensagem porque está inscrito no grupo "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.

--
---
Pedro Werneck

[Bruno Bkr]

Nossa cara,agora fiquei muitoooo impressionado(de verdade mesmo,sem ironia)!!! 

Primeiramente muitooo obrigado pela melhoria no meu alg,pois ficou muitooo show.

Em segundo lugar,que pedir desculpas pelos mal entendidos da minha parte até o momento.

Creio que vc me mostrou por A + B a real situação daquilo que propus,e sim,você tem razão noque diz respeito a eu ter superestimado este alg em relação a efeiciencia em gerar números primos,apesar das melhorias que você fez,a lógica em si do algoritmo não permite milagres,então ele para a finalidade de gerar números primos não é nenhuma revolução.

Por outro lado,como ja mencionei antes,a teoria por detrás deste algoritmo é que tenha me levado a superestimar tudo,pois particularmente achei a teoria muito interessante e "bela",não só pelo número 42,mas como um todo,é como se fosse engrenagens de um relógio que escondem os números primos,e esta beleza da teoria creio que é verdadeira e não vai se perder,pois para mim me diz muito no sentido filosófico,existencial e mistico,onde você novamente tem razão,aqui não é o lugar para discutir esse tipo de coisa.

Novamente obrigado,e no que diz respeito a parte computacional desta teoria creio ja ter chegado ao limite(ou proximo) graças as melhorias que você fez,e no demais estou cansado de quebrar a cabeça neste sentido(e me falta muita base de programação pra evoluir nesse sentido tambem),de agora em diante vou focar no sentido filosofico desta teoria,ou seja,não postarei aqui,rsrsrs,mas fica então,um novo crivo e metodo de encontrar primos,dentre muitos,e qualquer melhoria que alguem fizer,posta aqui que eu acompanho o forum,

Valeu a todos!!!