Verificar se um número é primo
Publicado por Israel Silvino Melo Batista (última atualização em 28/04/2015)
[ Hits: 9.793 ]
Implementa a função isprime que verifica se um número é primo.
Nota: o script não pode ser utilizado sozinho, você pode salvá-lo em: /usr/lib/python[versão do python]/
No meu caso: /usr/lib/python2.7/
E depois utilizá-lo em seus programas usando:
from primo import isprime
# -*- coding: utf-8 -*-
# Programa simples e eficiente que verifica se um número é primo
from math import sqrt
_author_ = "Israel S. Melo Batista (Israel77)"
def isprime(integer):
#Checa se um inteiro é primo
sq = sqrt(integer) # armazena a raiz quadrada da entrada na variável sq
if integer > 0 and integer == int(integer):
if integer == 2:
return True # 2 é o único primo par
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
else:
raise ValueError("input is not a positive integer")
Scripts recomendados
Visualizar a data e hora de um servidor SNTP e atualizar na BIOS do sistema
Criador de instalador USB Linux bootável com Python
Calculadora para números complexos
Comentários
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
[2] Comentário enviado por Israel77 em 29/04/2015 - 14:34h
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Obrigado pela sugestão
Eu tentei otimizar ao máximo o programa mas nem lembrei desse detalhe, vou testar sua versão pra ver se há um ganho significativo de desempenho, se sim vou substituir no futuro. Também pretendo incluir mais funções relacionadas a números primos.
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Obrigado pela sugestão
Eu tentei otimizar ao máximo o programa mas nem lembrei desse detalhe, vou testar sua versão pra ver se há um ganho significativo de desempenho, se sim vou substituir no futuro. Também pretendo incluir mais funções relacionadas a números primos.
[3] Comentário enviado por MattF em 04/05/2015 - 13:18h
[2] Comentário enviado por Israel77 em 29/04/2015 - 14:34h
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Obrigado pela sugestão
Eu tentei otimizar ao máximo o programa mas nem lembrei desse detalhe, vou testar sua versão pra ver se há um ganho significativo de desempenho, se sim vou substituir no futuro. Também pretendo incluir mais funções relacionadas a números primos.
Cara, um projeto muito interessante de se fazer é um algoritmo que deconponha qualquer número em números primos e mostre seus expoentes.
[2] Comentário enviado por Israel77 em 29/04/2015 - 14:34h
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Obrigado pela sugestão
Eu tentei otimizar ao máximo o programa mas nem lembrei desse detalhe, vou testar sua versão pra ver se há um ganho significativo de desempenho, se sim vou substituir no futuro. Também pretendo incluir mais funções relacionadas a números primos.
Cara, um projeto muito interessante de se fazer é um algoritmo que deconponha qualquer número em números primos e mostre seus expoentes.
[4] Comentário enviado por Israel77 em 06/05/2015 - 15:30h
[3] Comentário enviado por MattF em 04/05/2015 - 13:18h
[2] Comentário enviado por Israel77 em 29/04/2015 - 14:34h
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Obrigado pela sugestão
Eu tentei otimizar ao máximo o programa mas nem lembrei desse detalhe, vou testar sua versão pra ver se há um ganho significativo de desempenho, se sim vou substituir no futuro. Também pretendo incluir mais funções relacionadas a números primos.
Cara, um projeto muito interessante de se fazer é um algoritmo que deconponha qualquer número em números primos e mostre seus expoentes.
Realmente seria legal, já tenho até uma ideia de como fazer isso. Eu testei sua versão do programa. Quando eu uso a função isprime sozinha sua versão ainda fica substancialmente mais lenta do que usar o xrange de 2 em 2(mas é bem pouco). Porém quando eu uso a função para criar uma list comprehension aí já fica mais rápido em relação ao xrange.
[3] Comentário enviado por MattF em 04/05/2015 - 13:18h
[2] Comentário enviado por Israel77 em 29/04/2015 - 14:34h
[1] Comentário enviado por MattF em 28/04/2015 - 21:57h
Cara você poderia checar somente o dois e andar de ímpar a ímpar. Afinal se um número é divisível por 2, não precisa testar se ele é divisível por 4, 6, qualquer_par.
Eu trocaria:
[code]
for i in xrange(2, integer):
if integer % i == 0: # se o número tem um divisor ...
return False # então ele não é primo
if i > sq:
return True
[/code]
por:
[code]
i=2
while True:
if integer % i == 0:
return False
break
if i > sq:
return True
break
if i >= 3:
i=i+2
else:
i=3
[/code]
O que praticamente dobra a velocidade, pelo menos reduz o número de processos notávelmente.
Acho que é o máximo que dá para otmizar.
Obrigado pela sugestão
Eu tentei otimizar ao máximo o programa mas nem lembrei desse detalhe, vou testar sua versão pra ver se há um ganho significativo de desempenho, se sim vou substituir no futuro. Também pretendo incluir mais funções relacionadas a números primos.
Cara, um projeto muito interessante de se fazer é um algoritmo que deconponha qualquer número em números primos e mostre seus expoentes.
Realmente seria legal, já tenho até uma ideia de como fazer isso. Eu testei sua versão do programa. Quando eu uso a função isprime sozinha sua versão ainda fica substancialmente mais lenta do que usar o xrange de 2 em 2(mas é bem pouco). Porém quando eu uso a função para criar uma list comprehension aí já fica mais rápido em relação ao xrange.
[5] Comentário enviado por removido em 18/05/2015 - 05:16h
Outra coisa que dá prá fazer é verificar até a raiz quadrada do número.
Por exemplo: 101. Raiz quadrada 10. Você testa apenas com 2, 3, 5, 7 e 9. É isso que se faz no crivo de Erastótenes.
Aliás nem 9 se você estiver armazenando primos em uma tabela. É que se é divisível por 9 então é divisível por 3 e você já testou o 3. Se for ver no crivo manual, o 9 já foi riscado.
Use listas em python Ou tuplas. Não me lembro agora do nome técnico que dão prá essa estrutura de dados em python.
--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden
Outra coisa que dá prá fazer é verificar até a raiz quadrada do número.
Por exemplo: 101. Raiz quadrada 10. Você testa apenas com 2, 3, 5, 7 e 9. É isso que se faz no crivo de Erastótenes.
Aliás nem 9 se você estiver armazenando primos em uma tabela. É que se é divisível por 9 então é divisível por 3 e você já testou o 3. Se for ver no crivo manual, o 9 já foi riscado.
Use listas em python Ou tuplas. Não me lembro agora do nome técnico que dão prá essa estrutura de dados em python.
--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden
[6] Comentário enviado por Israel77 em 18/05/2015 - 15:58h
[5] Comentário enviado por listeiro_037 em 18/05/2015 - 05:16h
Outra coisa que dá prá fazer é verificar até a raiz quadrada do número.
Por exemplo: 101. Raiz quadrada 10. Você testa apenas com 2, 3, 5, 7 e 9. É isso que se faz no crivo de Erastótenes.
Aliás nem 9 se você estiver armazenando primos em uma tabela. É que se é divisível por 9 então é divisível por 3 e você já testou o 3. Se for ver no crivo manual, o 9 já foi riscado.
Use listas em python Ou tuplas. Não me lembro agora do nome técnico que dão prá essa estrutura de dados em python.
--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden
Cara, mas eu só verifico até a raiz quadrada, tá nesse trecho do código:
[code]
if i > sq:
return True
[/code]
Armazenar os primos em uma tupla(sim, é esse o nome de uma lista imutável ^^) também pensei no começo, mas depois achei que seria meio complicado.
[5] Comentário enviado por listeiro_037 em 18/05/2015 - 05:16h
Outra coisa que dá prá fazer é verificar até a raiz quadrada do número.
Por exemplo: 101. Raiz quadrada 10. Você testa apenas com 2, 3, 5, 7 e 9. É isso que se faz no crivo de Erastótenes.
Aliás nem 9 se você estiver armazenando primos em uma tabela. É que se é divisível por 9 então é divisível por 3 e você já testou o 3. Se for ver no crivo manual, o 9 já foi riscado.
Use listas em python Ou tuplas. Não me lembro agora do nome técnico que dão prá essa estrutura de dados em python.
--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden
Cara, mas eu só verifico até a raiz quadrada, tá nesse trecho do código:
[code]
if i > sq:
return True
[/code]
Armazenar os primos em uma tupla(sim, é esse o nome de uma lista imutável ^^) também pensei no começo, mas depois achei que seria meio complicado.
[7] Comentário enviado por removido em 18/05/2015 - 21:29h
Ah, sim. Esqueci e acabei detalhando demais ...
Sorry.
--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden
Ah, sim. Esqueci e acabei detalhando demais ...
Sorry.
--
Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Atualizando o Passado: Linux no Lenovo G460 em 2025
aaPanel - Um Painel de Hospedagem Gratuito e Poderoso
O macete do Warsaw no Linux Mint e cia
Dicas
Um modo leve de ouvir/ver áudio/vídeo da internet em máquinas pererecas
Resolver algumas mensagens de erro do SSH
Instalar módulo de segurança do Banco do Brasil Warsaw do tipo .run
Tópicos
Sem espaço na partição home (2)
O que você está ouvindo agora? [2] (190)
Procrastinação e autossabotagem são problemas muito comuns na sociedad... (5)
Top 10 do mês
-
Xerxes
1° lugar - 72.520 pts -
Fábio Berbert de Paula
2° lugar - 50.303 pts -
Daniel Lara Souza
3° lugar - 17.581 pts -
Mauricio Ferrari
4° lugar - 16.974 pts -
Alberto Federman Neto.
5° lugar - 14.114 pts -
Buckminster
6° lugar - 14.081 pts -
edps
7° lugar - 13.811 pts -
Diego Mendes Rodrigues
8° lugar - 12.715 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
9° lugar - 12.569 pts -
Andre (pinduvoz)
10° lugar - 12.388 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
