Gerador de numeros primos

[adf....@terra.com.br]

Ola.

Gostaria que alguem me ajuda-se na solução desse problema.

Estou usando um Script original de Marco Andre Lopes Mendes é um gerador de numeros primos, que começa a gerar apartir de 2.

Já cheguei a 2326022257(09 Digitos), o Scrit é rapido mais mesmo assim vai demorar eu pretendo chegar a 1 milhão de digitos.

Bom a pergunta é seguinte, eu tenho como começar de onde eu parei ao inves de 2?

|| http://pastebin.com/3bNjcLAm || 

[Danillo Souza]

Cara, acredito que não haja grande coisa que possa ser feito a respeito disso, já que encontrar números primos é um problema cujo tempo de resposta aumenta exponencialmente a cada novo número. Números primos são parte chave dos sistemas de criptografia justamente por isso: não são tão rápidos de serem encontrados.

O maior número primo já encontrado, se não me engano, tem por volta de 17.5 milhões de dígitos, então não acho que haja uma forma de fazer isso ser tão rápido quanto você quer.

Se eu estiver errado, por favor, me iluminem. ;)

--
--
------------------------------------
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 a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para python-brasi...@googlegroups.com.
Para obter mais opções, acesse https://groups.google.com/groups/opt_out.

[adf....@terra.com.br]

O professor de matemática Curtis Cooper, da Universidade do Missouri (Estados Unidos) anunciou esta semana ter descoberto o maior número primo até hoje conhecido. Escreve-se "2 elevado a 57.885.161 -1" e tem 17 milhões de dígitos.

Numero completo Aqui; || http://prime.toldyouso.com/digit/m57885161/prime-c.html || 

Aproveitando sua deixa eu achei outro script do mesmo autor que diz ser mais rapido a geração de numeros || http://pastebin.com/pTexYE02 || ele sugero usar "Para mostrar todos os primos abaixo de 1000, use meu_primos(1000). Esse algoritmo chega a ser umas 20 vezes mais rápido do que o descrito acima."  ( o de cima é que está aqui em baixo)  || http://pastebin.com/3bNjcLAm || 

Só que sou leigo iniciante em pytho não sei como implementar.

Grato

Antonio Donato Filho

Em Seg 2/12/13 09:07, Danillo Souza danil...@gmail.com escreveu:

Cara, acredito que não haja grande coisa que possa ser feito a respeito disso, já que encontrar números primos é um problema cujo tempo de resposta aumenta exponencialmente a cada novo número. Números primos são parte chave dos sistemas de criptografia justamente por isso: não são tão rápidos de serem encontrados.

O maior número primo já encontrado, se não me engano, tem por volta de 17.5 milhões de dígitos, então não acho que haja uma forma de fazer isso ser tão rápido quanto você quer.

Se eu estiver errado, por favor, me iluminem. ;)

Em 1 de dezembro de 2013 14:49, <adf....@terra.com.br> escreveu:

[Helder]

Ok, então o primeiro passo lógico para vc seria aprender o mínimo da linguagem[1].

[1] http://turing.com.br/pydoc/2.7/tutorial/

Boa sorte.

Helder C. R. de Oliveira
http://helderc.net

[adf....@terra.com.br]

É exatamente o que estou fazendo aqui!!!!!

Em Seg 2/12/13 09:56, Helder held...@gmail.com escreveu:

Ok, então o primeiro passo lógico para vc seria aprender o mínimo da linguagem[1].

[1] http://turing.com.br/pydoc/2.7/tutorial/

Boa sorte.

Em 2 de dezembro de 2013 09:27, <adf....@terra.com.br> escreveu:

--

Helder C. R. de Oliveira
http://helderc.net

[Danillo Souza]

O que você precisa, nesse caso, é salvar o estado do script em execução, para da próxima vez que rodar ele continuar de onde parou ao invés de começar tudo denovo, certo?

Se for isso, você pode salvar o estado num arquivo texto/json/pickle (depende do que for melhor no seu caso, não vi sua implementação) e sempre que rodar o script, primeiro verificar se existe algum estado salvo. Se existir, carrega esse estado e continua de onde parou, senão começa do zero.

[adf....@terra.com.br]

OK obrigado, por enquanto.

Em Seg 2/12/13 10:39, Danillo Souza danil...@gmail.com escreveu:

O que você precisa, nesse caso, é salvar o estado do script em execução, para da próxima vez que rodar ele continuar de onde parou ao invés de começar tudo denovo, certo?

Se for isso, você pode salvar o estado num arquivo texto/json/pickle (depende do que for melhor no seu caso, não vi sua implementação) e sempre que rodar o script, primeiro verificar se existe algum estado salvo. Se existir, carrega esse estado e continua de onde parou, senão começa do zero.

[Kayro]

E se arrancarem da linguagem o : do final do bloco. Fica mais rápido?

[Danillo Souza]

Thread errada cara.

[adf....@terra.com.br]

assim fica mais rapido || http://pastebin.com/Y3Ft7Y5H ||

Falta fazer com que que ele reinicie de onde parou, como no Hydra vc para e depois digita Hidra -R e ele recomeça de onde parou 

Em Seg 2/12/13 13:18, Kayro tagg...@gmail.com escreveu:

E se arrancarem da linguagem o : do final do bloco. Fica mais rápido?

[Alysson Gonçalves de Azevedo]

Sou programador de outras linguagens e assino a lista por curiosidade, então não sei muito sobre python, mas pelo que vi, a variavel idx começa de zero até chegar no valor de idx_sqrtn, então, se você salvar o idx e depois inicializar o idx com valor salvo, em vez de zero, o calculo continuará a partido ponto anterior, como você quer.

O problema é que o vetor nums vai se perder, e como salvar e recuperar os dados dele depois, eu não sei como fazer.

Alysson Gonçalves de Azevedo

"Anarcho-syndicalism is a way of preserving freedom." - Monty Python

[adf....@terra.com.br]

Vale!

Em Seg 2/12/13 14:32, Alysson Gonçalves de Azevedo agal...@gmail.com escreveu:

Sou programador de outras linguagens e assino a lista por curiosidade, então não sei muito sobre python, mas pelo que vi, a variavel idx começa de zero até chegar no valor de idx_sqrtn, então, se você salvar o idx e depois inicializar o idx com valor salvo, em vez de zero, o calculo continuará a partido ponto anterior, como você quer.

O problema é que o vetor nums vai se perder, e como salvar e recuperar os dados dele depois, eu não sei como fazer.

Alysson Gonçalves de Azevedo

"Anarcho-syndicalism is a way of preserving freedom." - Monty Python

[Danillo Souza]

Você vai precisar modificar a sua função de forma que ela aceiteum valor inicial para as variáveis n e primos (o último primo que você achou, e o array com todos os primos).

Nesse caso, o que eu te aconcelho a fazer para gravar esses dados, é montar um dicionário e serializar com Pickle. Algo como:

import pickle

def save_state(n, primos, arquivo):

    saved_state = {"n": n, "primos": primos}

    output = open(arquivo, 'wb')

    pickle.dump(data, output)

def recover_state(arquivo):

    source = open(arquivo, 'rb')

    data = pickle.load(source)

    return data

Para salvar o estado, na saída do programa você faria algo como:

save_state(n, primos, 'estado.bkp')

E para recuperar esses dados na inicialização do script:

import os

arquivo = 'estado.bkp'

if os.path.isfile(arquivo):

    data = recover_state('estado.bkp')

    # chama função passando data['n'] e data['primos']

else:

    # chama a função normalmente

Mas como eu disse, você vai ter que adaptar sua função para funcionar assim.

[adf....@terra.com.br]

Grato.

Em Seg 2/12/13 14:44, Danillo Souza danil...@gmail.com escreveu:

Você vai precisar modificar a sua função de forma que ela aceiteum valor inicial para as variáveis n e primos (o último primo que você achou, e o array com todos os primos).

Nesse caso, o que eu te aconcelho a fazer para gravar esses dados, é montar um dicionário e serializar com Pickle. Algo como:

import pickle

def save_state(n, primos, arquivo):

    saved_state = {"n": n, "primos": primos}

    output = open(arquivo, 'wb')

    pickle.dump(data, output)

def recover_state(arquivo):

    source = open(arquivo, 'rb')

    data = pickle.load(source)

    return data

Para salvar o estado, na saída do programa você faria algo como:

save_state(n, primos, 'estado.bkp')

E para recuperar esses dados na inicialização do script:

import os

arquivo = 'estado.bkp'

if os.path.isfile(arquivo):

    data = recover_state('estado.bkp')

    # chama função passando data['n'] e data['primos']

else:

    # chama a função normalmente

Mas como eu disse, você vai ter que adaptar sua função para funcionar assim.

[Danilo J. S. Bellini]

Por conta do grupo no Facebook, eu fiz isso há algum tempo

https://gist.github.com/danilobellini/7233352

O link contém um gerador sequencial de números primos (o "prime_gen") sem um limite inicial predeterminado, e sem ficar se preocupando com os números pares depois do 2.
Acho que isso pode ajudar com a questão do armazenamento e com o "continuar de onde parou".

Danilo J. S. Bellini
---------------
"It is not our business to set up prohibitions, but to arrive at conventions." (R. Carnap)

[Marcelo Elias Del Valle]

Estou chegando meio atrasado à thread, mas vou tentar dar meus 2 cents:

tem uma teoria que diz que um número é primo e não for divisível por todos os primos anteriores a ele. Se você utilizar memória para guardar os primos anteriores ao número e em conjunto com as outras teorias (como não verificar números multiplos de 2 ou 3 ou maiores que a raiz do número) pode conseguir resultados interessantes.

[]s

[Danilo J. S. Bellini]

Marcelo, é o que a solução que mandei faz. =)

Depois de gerar o 2, ela ignora totalmente os números pares, usando para isso um contador de números ímpares, e verifica a divisibilidade somente com os números primos <= à raiz quadrada do novo número (sempre a partir do 3). Porém é mais eficiente verificar o "<=" usando quadrados de números inteiros do que calculando raizes.

E agora fiquei pensativo sobre o que seria mais rápido para armazenar os números primos em ordem: a list como está na solução ou uma collections.deque (trocando a linha 26)?

--
--
------------------------------------
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 a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para python-brasi...@googlegroups.com.
Para obter mais opções, acesse https://groups.google.com/groups/opt_out.

[Marcelo Elias Del Valle]

Olá Danilo, 

     Por algum motivo, o código que você mandou no pastebin deve estar chegando desatualizado, pq aqui não tem linha 26, só 24 linhas.  De qualquer forma, dei uma olhada no collections.deque e pareceu um vetor com realocação dinâmica (legal, não conhecia!). Independente de qual estrutura dessas vc use, tudo terá de ser carregado na memória, então eu usária um vetor mesmo, já que você conhece de antemão a qtd de primos que quer consultar. Se bem que vc não quer os primeiros milhões de primos e sim os primos até x dígitos né...  Anyway, usando um vetor você não só aproveita melhor a memória como acessa os elementos mais rapidamente, então eu daria um jeito de usar alguma estrutura assim...

     Não sei se existe no python, mas poderia ser usada uma hash table (map) onde a chave é o elemento inicial do vetor e o valor é o vetor em si. Então se i estiver entre 1 e 100000, por exemplo, está na hash 1. Se estiver entre 100001 e 200000, na hash 100001... É uma maneira de vc combinar um acesso rápido com crescimento aleatório.

     Mas enfim, isso tudo já são viagens da minha cabeça. Show de bola o problema dos primos!

Abraços,

Marcelo.

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

Para obter mais opções, acesse https://groups.google.com/groups/opt_out.

--
Marcelo Elias Del Valle
http://mvalle.com - @mvallebr

[Danilo J. S. Bellini]

Marcelo, acho que você pegou outro link enviado aqui na lista, eu não mandei nada no pastebin, mandei no Gist do GitHub:

https://gist.github.com/danilobellini/7233352

Com realce na linha 26:

https://gist.github.com/danilobellini/7233352#file-divisors-py-L26

Esse código tem 56 linhas.

O collections.deque é ineficiente para uso próximo à posição central, mas eficiente para uso (inserção/remoção/acesso) próximo às extremidades. É bastante útil para uso como fila ou como fila circular (possui métodos appendleft e popleft, parâmetro maxlen, etc.).

Não entendi por que se preocupar com hash nesse caso...se for para conveniência, nada proibe você de usar um dicionário...se for por conta de desempenho para verificar se um elemento M está no conjunto dos números primos até N, sendo N >= M, você pode usar um set() sobre o resultado (i.e., fora da função que encontra os números primos).

Eu não usei isso no gist, mas você poderia sim usar um set() na linha 26. Porém isso pioraria o desempenho por exigir a verificação com todos os primos anteriores (não apenas os menores que a raiz quadrada), já que a ordenação seria perdida (em um conjunto, os elementos não estão "ordenados"). A linha 30 teria de usar um add ao invés de append, e o laço da linha 29 tem de usar o conjunto mesmo, não iter_primes, pois esse iterável com o takewhile foi feito pensando que os números primos encontrados fossem armazenados em ordem ascendente.

[Marcos Thomaz]

Em C/C++, o uso de operadores binários em algumas operações também melhora um pouco o desempenho... nas operações que envolvem a divisão por 2 que estão no código talvez seja interessante fazer a substituição, visto que são consideradas apenas as partes inteiras da divisão; usando a divisão por 2 poderia ser abortado o loop quando se está tentando comparar valores maiores que a metade do número + 1. Por exemplo, se estamos tentando verificar se um número X é primo, dado que K seja um valor anterior, poderia ser feita uma verificação assim:

if K > (X >> 1) :  break

--
--
------------------------------------
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 a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para python-brasi...@googlegroups.com.
Para obter mais opções, acesse https://groups.google.com/groups/opt_out.

--

Marcos Thomaz da Silva

Analista de Tecnologia da Informação

[adf....@terra.com.br]

Demorou 25 minutos, usando os dois scripts. 

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

C:\Users\****>python  divisors.py

Type in a positive integer number: 40567757

40567757 | 40567757

       1 | -

Com esse script 15 segundos || http://pastebin.com/EqE1XNXn ||

C:\Users\****>python Numero-primo.py

Digite um numero positivo real qualquer: 40567757

-> E divisivel por 1 <-

--> E divisivel por 40567757 <--

O numero requisitado e primo!

Em Ter 3/12/13 11:24, Danilo J. S. Bellini danilo....@gmail.com escreveu:

Marcelo, acho que você pegou outro link enviado aqui na lista, eu não mandei nada no pastebin, mandei no Gist do GitHub:

https://gist.github.com/danilobellini/7233352

Com realce na linha 26:

https://gist.github.com/danilobellini/7233352#file-divisors-py-L26

Esse código tem 56 linhas.

O collections.deque é ineficiente para uso próximo à posição central, mas eficiente para uso (inserção/remoção/acesso) próximo às extremidades. É bastante útil para uso como fila ou como fila circular (possui métodos appendleft e popleft, parâmetro maxlen, etc.).

Não entendi por que se preocupar com hash nesse caso...se for para conveniência, nada proibe você de usar um dicionário...se for por conta de desempenho para verificar se um elemento M está no conjunto dos números primos até N, sendo N >= M, você pode usar um set(sobre o resultado (i.e., fora da função que encontra os números primos).

Eu não usei isso no gist, mas você poderia sim usar um set() na linha 26. Porém isso pioraria o desempenho por exigir a verificação com todos os primos anteriores (não apenas os menores que a raiz quadrada), já que a ordenação seria perdida (em um conjunto, os elementos não estão "ordenados"). A linha 30 teria de usar um add ao invés de append, e o laço da linha 29 tem de usar o conjunto mesmo, não iter_primes, pois esse iterável com o takewhile foi feito pensando que os números primos encontrados fossem armazenados em ordem ascendente.

[Marcelo Elias Del Valle]

Danilo, 

     O tempo de acesso a uma hash é curto, mas quando é feito muuuuuuitas vezes calcular o hash pode ocupar uma parte considerável do tempo de processamento. Um vetor sempre será mais rápido, não tem jeito. Não é por conveniência, é para tentar economia cada fração de tempo... Mas é apenas uma das milhares de otimizações que possivelmente podem ser feitas.

     Sobre o set, não entendi, desculpe. Vou analisar melhor depois.

Abraços,

Marcelo.

[Marcelo Elias Del Valle]

Olha, crie um com o que eu queria dizer sobre a otimização 1:

http://pastebin.com/P7rwDm50

python primos.py 10

Verificando se 1 eh primo 

******> O numero 1 e primo!

Verificando se 2 eh primo 

******> O numero 2 e primo!

Verificando se 3 eh primo 

******> O numero 3 e primo!

Verificando se 4 eh primo 

-> E divisivel por 2 <- nao eh primo 

Verificando se 5 eh primo 

******> O numero 5 e primo!

Verificando se 6 eh primo 

-> E divisivel por 2 <- nao eh primo 

Verificando se 7 eh primo 

******> O numero 7 e primo!

Verificando se 8 eh primo 

-> E divisivel por 2 <- nao eh primo 

Verificando se 9 eh primo 

-> E divisivel por 9 <- nao eh primo 

Verificando se 10 eh primo 

-> E divisivel por 2 <- nao eh primo 

[Marcelo Elias Del Valle]

Adf, 

    Mas estamos falando da mesma coisa? Qual o objetivo, gerar os n primeiros primos ou verificar se n é primo? O segundo problema é sem comparação muito mais simples que o primeiro...

Abraços,

Marcelo.

[adf....@terra.com.br]

Gerar n Primos e se consegir um numero grande eu sei que não vou conseguir veriuficar o mesmo teria que apelar para o  

GIMPS http://www.mersenne.org/ ou outro .

Vou tentando aqui 

Grato

Marcelo


Em Ter 3/12/13 14:45, Marcelo Elias Del Valle mval...@gmail.com escreveu:

Adf, 

    Mas estamos falando da mesma coisa? Qual o objetivo, gerar os n primeiros primos ou verificar se n é primo? O segundo problema é sem comparação muito mais simples que o primeiro...

Abraços,

Marcelo.

Em 3 de dezembro de 2013 14:00, <adf....@terra.com.br> escreveu:

Demorou 25 minutos, usando os dois scripts. 

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

C:\Users\****>python  divisors.py

Type in a positive integer number: 40567757

40567757 | 40567757

       1 | -

Com esse script 15 segundos || http://pastebin.com/EqE1XNXn ||

C:\Users\****>python Numero-primo.py

Digite um numero positivo real qualquer: 40567757

-> E divisivel por 1 <-

--> E divisivel por 40567757 <--

O numero requisitado e primo!

Em Ter 3/12/13 11:24, Danilo J. S. Bellini danilo....@gmail.com escreveu:

Marcelo, acho que você pegou outro link enviado aqui na lista, eu não mandei nada no pastebin, mandei no Gist do GitHub:

https://gist.github.com/danilobellini/7233352

Com realce na linha 26:

https://gist.github.com/danilobellini/7233352#file-divisors-py-L26

Esse código tem 56 linhas.

O collections.deque é ineficiente para uso próximo à posição central, mas eficiente para uso (inserção/remoção/acesso) próximo às extremidades. É bastante útil para uso como fila ou como fila circular (possui métodos appendleft e popleft, parâmetro maxlen, etc.).

Não entendi por que se preocupar com hash nesse caso...se for para conveniência, nada proibe você de usar um dicionário...se for por conta de desempenho para verificar se um elemento M está no conjunto dos números primos até N, sendo N >= M, você pode usar um set(sobre o resultado (i.e., fora da função que encontra os números primos).

Eu não usei isso no gist, mas você poderia sim usar um set() na linha 26. Porém isso pioraria o desempenho por exigir a verificação com todos os primos anteriores (não apenas os menores que a raiz quadrada, já que a ordenação seria perdida (em um conjunto, os elementos não estão "ordenados"). A linha 30 teria de usar um add ao invés de append, e o laço da linha 29 tem de usar o conjunto mesmo, não iter_primes, pois esse iterável com o takewhile foi feito pensando que os números primos encontrados fossem armazenados em ordem ascendente.

[Marcelo Elias Del Valle]

Deixei rodando o meu script com a otimização 1 que eu tinha comentado, eis o resultado:

time python primos.py 40567757 > /tmp/teste

real 31m59.632s

user 31m39.283s

sys 0m3.628s

Esse foi o tempo para achar todos os primos entre 1 e 40567757.

Depois vou tentar modificá-lo e posto o resultado aqui tb.

[]s

[adf....@terra.com.br]

Posta o script , por favor.

Em Ter 3/12/13 16:13, Marcelo Elias Del Valle mval...@gmail.com escreveu:

Deixei rodando o meu script com a otimização 1 que eu tinha comentado, eis o resultado:

time python primos.py 40567757 > /tmp/teste

real 31m59.632s

user 31m39.283s

sys 0m3.628s

Esse foi o tempo para achar todos os primos entre 1 e 40567757.

Depois vou tentar modificá-lo e posto o resultado aqui tb.

[]s

[Marcelo Elias Del Valle]

Ops, foi mal! Esqueci de passar o link!

Segue o link com a otimização 1, que demorou 30 min na minha máquina.

http://pastebin.com/P7rwDm50

Agora com a otimização 3:

http://pastebin.com/Kwi3kimi

Resultado:

time python primos.py 40567757 > /tmp/teste2

real 13m18.956s

user 13m5.621s

sys 0m2.996s

Detalhe que eu não usei um generator, fiquei curioso em saber se há diferença em performance.

E também estou escrevendo em arquivo, não escrever deve agilizar bem. 

[]s

[adf....@terra.com.br]

Index_Error linha 11. (python 27)

erro sintaxe linha 10 (python 33

Falando serio eu estou no comecinho de python , 

se puder me ajudar será otímo>

Em Ter 3/12/13 16:42, Marcelo Elias Del Valle mval...@gmail.com escreveu:

Ops, foi mal! Esqueci de passar o link!

Segue o link com a otimização 1, que demorou 30 min na minha máquina.

http://pastebin.com/P7rwDm50

Agora com a otimização 3:

http://pastebin.com/Kwi3kimi

Resultado:

time python primos.py 40567757 > /tmp/teste2

real 13m18.956s

user 13m5.621s

sys 0m2.996s

Detalhe que eu não usei um generator, fiquei curioso em saber se há diferença em performance.

E também estou escrevendo em arquivo, não escrever deve agilizar bem. 

[]s

[Marcelo Elias Del Valle]

Adf, em quel arquivo foi isso?

aqui ambos rodaram ok, não é identação?

[]s

[Danilo J. S. Bellini]

Isso está confuso, para dizer o mínimo.

@adf,
Como o Marcelo disse, não estamos falando/fazendo a mesma coisa. O script que forneci não procura primos, ele procura todos os divisores de um número, e para isso ele possui internamente um gerador de números primos (o prime_gen). Se simplesmente verificar que um número é primo fosse equivalente à decomposição em seus divisores, teríamos sérios problemas com criptografia...e viva o P = NP...

Os 15 segundos do script de simples verificação poderia ser reduzido caso separássemos um tempo de "loading" (geração dos números primos) de sua posterior verificação usando um set. A duração resultante de algo como "40567757 in set_primos" seria ínfima nesse caso. Isso seria útil no caso em que há muitos números a serem verificados (amortização do tempo de geração dos números primos pelo número de consultas realizadas).

@Marcelo,

"Não é por conveniência, é para tentar economia cada fração de tempo"

Ótimo. Entendi que você quer otimizar a estrutura de dados. Mas recomendo que utilize as estruturas já fornecidas com o Python, raramente você sentirá falta de algo, e se precisar de algo otimizado nesse nível o melhor talvez seja procurar quem já fez (e.g. vetores com array.array ou com o numpy), ou então fazer direto em C (para ser usado no Python). No C você pode decidir se a organização interna de uma sequência que você quer armazenar será um segmento contíguo de memória, uma lista ligada ou alguma combinação de ambos em "buckets", tomando as devidas preocupações para não termos segmentation faults e coisas do gênero. Mas se eu consegui fazer um efeito de phaser variante no tempo funcionar em tempo real no CPython na taxa de 44100 amostras por segundo usando apenas Python puro, fico pensativo quanto à necessidade de tanta otimização. Antes de tentar mexer com extensões em C, melhor tentar outras coisas (e.g. rodar no pypy).

Sobre o motivo de eu ter falado sobre "set", tente fazer isto:

a = set([1, 2, 3])

Tudo ok, mas porque isto:

b = set([[1, 2, 3]])

e isto:

c = set([a])

nâo "funciona"? Dica:

http://docs.python.org/3/library/stdtypes.html#set

http://docs.python.org/3/glossary.html#term-hashable
http://docs.python.org/3/library/functions.html#hash
http://docs.python.org/3/reference/datamodel.html#object.__hash__

Deixei rodando aqui um script para verificar com list e com deque qual é mais rápido. Em 30 segundos, obtive:

Duration (for each generator): 30 seconds
Prime found with a list for storage: 5074189
Prime found with a deque for storage: 5096381

Em que o "Prime found" refere-se ao último primo encontrado dentro da citada faixa de tempo. Em 5 minutos (mas dessa vez comigo usando o computador...Firefox aberto...):

Duration (for each generator): 300 seconds
Prime found with a list for storage: 29119483
Prime found with a deque for storage: 29228581

Em 10 minutos (novamente, comigo usando o computador):

Duration (for each generator): 600 seconds
Prime found with a list for storage: 48929887
Prime found with a deque for storage: 48683143

Com o pypy (aqui é um Arch Linux):

Python 2.7.3 (6c8420e89b80b4c90720115e31c2793ba7fff08d, Nov 15 2013, 18:31:06)
[PyPy 2.2.0 with GCC 4.8.2] on linux2

Obtive em 10 segundos:

Duration (for each generator): 10 seconds
Prime found with a list for storage: 10884449
Prime found with a deque for storage: 6257981

O que é mais que o resultado em 30 segundos com o CPython.

Mas nos 10 minutos com o CPython, o script já havia passado do valor desejado. A "inversão" nos valores na avaliação de 10 minutos é muito pequena e pode ter sido resultado de meu uso do computador...seria legal vocês testarem na máquina de vocês, deixando-a dedicada a essa tarefa. Coloquei o código que gerou essas strings acima junto ao gist já fornecido (é só trocar a linha 35 pela duração desejada):

https://gist.github.com/danilobellini/7233352

[adf....@terra.com.br]

A indentação está correta não ha aviso de indentação inesperada.
uso: Primos.py NUMERO_LIMITE
Traceback (most recent call last):
  File "Primos.py", line 11, in <module>
    limite = int(sys.argv[1])
IndexError: list index out of range
|| http://pastebin.com/Kwi3kimi  |

Em Ter 3/12/13 16:51, adf....@terra.com.br escreveu:

Index_Error linha 11. (python 27)

erro sintaxe linha 10 (python 33

Falando serio eu estou no comecinho de python , 

se puder me ajudar será otímo>

Em Ter 3/12/13 16:42, Marcelo Elias Del Valle mval...@gmail.com escreveu:

Ops, foi mal! Esqueci de passar o link!

Segue o link com a otimização 1, que demorou 30 min na minha máquina.

http://pastebin.com/P7rwDm50

Agora com a otimização 3:

http://pastebin.com/Kwi3kimi

Resultado:

time python primos.py 40567757 > /tmp/teste2

real 13m18.956s

user 13m5.621s

sys 0m2.996s

Detalhe que eu não usei um generator, fiquei curioso em saber se há diferença em performance.

E também estou escrevendo em arquivo, não escrever deve agilizar bem. 

[]s

[Marcelo Elias Del Valle]

Adf, faltou o exit no meu script quando vc não passa os argumentos...

vc deve executar algo como 

python primos.py 100

Tem que passar um argumento para o programa.

[]s

[Marcelo Elias Del Valle]

Danilo, 

     Concordo, num caso real, faria em C chamando do python ou usaria pypy. Na verdade, é o que estamos pensando em fazer para os algorítmos que rodamos aqui na empresa.

     Não conheço muito as estruturas do python, mas pelos seus testes, parece que o dequeu é pior para grandes qtds de dados... Fiquei realmente curioso, vou dar uma estudada melhor depois. Vou tentar rodar seu algorítmo aqui e comparar com o que eu fiz, sem os geradores. Tem coisas que eu realmente ainda não entendo bem no python sobre o que está acontecendo "under the hood".

     Alías, aproveitando o ensejo, existe alguma referência das estruturas de dados disponíveis no python ou algo assim? Eu estava querendo treinar algorítmos e python ao mesmo tempo tentando resolver alguns problemas em python e tentando fazer uso de estruturas de dados variadas, como você fez nesse caso. 

     Se eu me deparar com algum problema interessante, está no escopo dessa lista discutir soluções de algorítmos em python? Particularmente gosto bastante de problemas como esses dos primos, são a melhor forma de melhorar ou desenferrujar bons skills de programação.

Abraços,

Marcelo.

[Renzo Nuccitelli]

Não tem nada a ver com melhora de performance, mas acho muito elegante a solução do Crivo de Erastótenes para quando se sabe o limite superior abaixo do qual se quer a lista dos primos. Escrevi o código por diversão:

https://gist.github.com/anonymous/7782423

Abs,

 

--
  Renzo Nuccitelli

  www.python.pro.br

[Renzo Nuccitelli]

Em 4 de dezembro de 2013 00:52, Marcelo Elias Del Valle <mval...@gmail.com> escreveu:

Se eu me deparar com algum problema interessante, está no escopo dessa lista discutir soluções de algorítmos em python? Particularmente gosto bastante de problemas como esses dos primos, são a melhor forma de melhorar ou desenferrujar bons skills de programação.

Com certeza está no escopo, e não duvido que esses é um dos assuntos que a turma mais gosta por aqui =D.

[Rubens Prates]

Marcelo, o capítulo de exemplo do livro "Python Cookbook" disponível para donwload gratuito (http://www.novatec.com.br/livros/python-cookbook/capitulo9788575223321.pdf) trata justamente de estrutura de dados e algoritmos em Python.

-- 
Rubens Prates

Editor | Novatec Editora

11 2976-8773 | rubens...@me.com

[Marcelo Elias Del Valle]

Nossa, que show o link Renzo! show de bola mesmo, valeu!

[]s

[Marcelo Elias Del Valle]

Cara, foi direto pro meu kindle! Vc me economizou umas horas de busca pelo material!

[]s