Verificador de números primos

Programa desenvolvido em Python que recebe um numero real positivo e verifica se o mesmo é primo. A ideia é optimizar esse processo ao máximo, portanto, contribuições serão muito bem vindas.

lestatwa

Por Luis Eduardo Boiko Ferreira em 13/09/2013

Homepage: https://www.facebook.com/luiseduardo.boiko

Hits: 55.358 Categoria: Python Subcategoria: Miscelânea

Descrição

Programa desenvolvido em Python que recebe um numero real positivo e verifica se o mesmo é primo. A ideia é optimizar esse processo ao máximo, portanto, contribuições serão muito bem vindas.

Download primo.py Enviar nova versão

Versões atualizadas deste script

Versão 2 enviada por Guilherme em 12/11/2011

Changelog: #/usr/bin/env python
#coding: utf-8
#Algoritmo para calcular se um numero é primo
#Autor: Luis Eduardo Boiko Ferreira
#Modifique o código a vontade, desde que mantenha o nome do autor
entrada = int(input("Digite um numero positivo real qualquer: "));
if (entrada <=0):
finalizar = str(input('Numero invalido, pressione qualquer tecla para continuar...'));
exit();

# i sera nosso divisor inicial
i = 1;
# j sera nosso contador de ocorrências
j = 0;

#Nenhum numero real vai ser divisivel por um numero maior do que sua metade
entrada1 = (entrada/2);

while (i <= entrada):

if (entrada % i==0):
print ('-> É divisivel por %i <-'%i);
i = i+1;
j = j+1;

if (i>=entrada1):
# damos a i, o valor da variavel entrada, pois o próximo divisor sera o próprio número
i = entrada;
print ('--> É divisivel por %i <--'%i);
i = i+1;
j = j+1;

else:
i = i+1;
if(j==2):
print ('O número requisitado é primo!');

else:
print ('Numero não é primo, possui',j,'divisores.');

Download Numero-primo.py

Versão 3 enviada por Fabio Pereira do Nascimento em 12/09/2013

Changelog: Script em Python para verificar se um número é primo.

Download n-primo.py

Esconder código-fonte

#/usr/bin/env python
#coding: utf-8
#Algoritmo para calcular se um numero é primo
#Autor: Luis Eduardo Boiko Ferreira
#Modifique o código a vontade, desde que mantenha o nome do autor

entrada = input("Digite um numero positivo real qualquer: ");
if (entrada <=0):
   finalizar = raw_input('Numero invalido, pressione qualquer tecla para continuar...');
   exit();

# i sera nosso divisor inicial
i = 1;
# j sera nosso contador de ocorrências
j = 0;

#Nenhum numero real vai ser divisivel por um numero maior do que sua metade
entrada1 = (entrada/2);

while (i <= entrada):

   if (entrada % i==0):
      print '-> É divisivel por',i,'<-';
      i = i+1;
      j = j+1;

   if (i>=entrada1):
      # damos a i, o valor da variavel entrada, pois o próximo divisor sera o próprio número
      i = entrada;
      print '--> É divisivel por',i,'<--';
      i = i+1;
      j = j+1;

   else:
      i = i+1;
if(j==2):
   print 'O número requisitado é primo!';

else:
   print 'Numero não é primo, possui',j,'divisores.';

Leitura recomendada

Just Do It - XML Generic Editor

Previsão do tempo - Py3K

Simulador de Empréstimos

Sudoku

Coquetel

Comentários

#1 Comentário enviado por Zaraki em 14/11/2011 - 22:28h

você já fez alguma análise em termos dos custos computacionais?

#2 Comentário enviado por lestatwa em 15/11/2011 - 20:38h

Olá Kyouraku. Este código foi publicado antes de eu estar cursando matemática.... tenho estudado mais a fundo e existem maneiras bem mais "leves" de se calcular primos....provavelmente eu publicarei qlqr dia destes uma versao bem mais agil!
Abraço!

#3 Comentário enviado por gui-gui em 16/11/2011 - 13:44h

Eu fiz uma versão bem mais leve em python tb, baseada neste código:http://www.vivaolinux.com.br/script/Numero-Primo-1

#4 Comentário enviado por fabioyast em 01/09/2013 - 20:02h

#!/usr/bin/python3
#Verifica se é um número primo (primo= é unicamente divisivel por 1 e por ele próprio)
while True:
try:
np = int(input("Entre com um número inteiro:" ))
for x in range(2, np+1):
x2 = np/x
if x2.is_integer() == True and np != x:
print(np,"não é número primo, tente novamente!")
break
elif x2.is_integer() == True and np == x:
print(np,"é número primo!!!")
except KeyboardInterrupt:
print()
exit(0)
except ValueError:
print("Valor digitado incorreto")
pass

#5 Comentário enviado por fabioyast em 12/09/2013 - 16:59h

[4] Comentário enviado por fabioyast em 01/09/2013 - 20:02h:

#!/usr/bin/python3
#Verifica se é um número primo (primo= é unicamente divisivel por 1 e por ele próprio)
while True:
try:
np = int(input("Entre com um número inteiro:" ))
for x in range(2, np+1):
x2 = np/x
if x2.is_integer() == True and np != x:
print(np,"não é número primo, tente novamente!")
break
elif x2.is_integer() == True and np == x:
print(np,"é número primo!!!")
except KeyboardInterrupt:
print()
exit(0)
except ValueError:
print("Valor digitado incorreto")
pass

#6 Comentário enviado por RenatoAlencar73 em 13/09/2013 - 19:20h

Ta todo mundo usando codigo d+, essa função lambda retorna True se n for primo: lambda isPrimo(n): True if [1,n] == [i for i in range(1,n) if (n%i)==0]

#7 Comentário enviado por fibean em 15/09/2013 - 20:15h

Na verdade o maior divisor que precisa ser testado pelo código é a raiz do numerador (sqrt(x)), e não a metade (x/2). Isso reduziria o custo computacional aos montes. Se for possível testar somente os números ímpares (somando ao denominador 2 ao invés de 1 à cada iteração) o número de divisões seria reduzido à metade+1.

Suponho que essa seria a maneira mais eficaz possível.

#8 Comentário enviado por xgrind em 17/04/2014 - 10:57h

Muito código a toa!

# Verificador de numero primo
i,cont = 1,0

n = int(raw_input('Digite o numero: '))

while i <= n:
if (n % i == 0):
cont += 1
i += 1

if cont == 2:
print '%d eh primo' % n
else:
print '%d nao eh primo' % n

Descrição

Versões atualizadas deste script

Leitura recomendada

Comentários

Contribuir com comentário