Python : matemática : números primos

segunda-feira, 27/02/2012 2:32 pm

Esses dias realizando alguns exercícios matemáticos e algoritmos em python me deparei com um que me solicitou:

Implementar uma função que retorne verdadeiro se o número for primo (falso caso contrário). Testar de 1 a 100.

Bom primeira coisa que fiz foi pensar em dividir esta atividade em 2 funções, uma para realizar a interação dos números e dentro chamar outra função para validar um respectivo número solicitado, sendo o retorno dessa função Verdadeiro (é um número primo) ou Falso (não é um número primo)

Sabendo que os números primos possuem a regra que os definem:

Um número primo é aquele que é divisível por apenas 2 números, 1 e por ele mesmo. Sabe-se também que o número 1, não é primo pois possui apenas um único divisor. O único número par que é primo é o número 2.

Tendo em mente o conhecimento geral sobre os números primos, implementei 2 versões de validação de número primo, a primeira versão uma varredura, dentro do universo dos números ímpares (verificaNumeroPrimoV1), inicialmente sem nenhuma otimização, porém após algumas leituras evoluí até a situação que será apresentada a seguir. Também implementei uma segunda versão de validação dos números primos dentro do universo de números ímpares (verificaNumeroPrimoV2), onde neste realizado uma validação verificando se o resto da divisão é zero e o divisor é diferente do número a ser validado, o que define que o número não é primo, e uma segunda checagem que valida se o Quociente da divisão é menou ou igual ao divisor, o que define que este número é um número primo.

Como comentei, após algumas leituras realizei umas otimizações, dentre elas:

- delimitei a validação até a raíz quadrada do número a ser validado

- verificação se o número possuí raíz quadrada, o que define que não é um número primo

- validação se o quociente da divisão do próximo número ímpar após a raíz quadrada do número é inferior ou igual ao divisor, o que define que o número validado é primo.

Com essas otimizações obtive o respectivo algoritmo:

Link do arquivo raw, no final do arquivo, tem um array com os números primos encontrados de 1 a 100000

Links de referência:

- Algoritmo em C

- Como identificar se um número é primo ou não? (verificação do quociente da divisão)

- Crivo de Eratóstenes

Veja também:

Zemanta

Cálculo, Matemática, Python

Fã

Muito bom!
Rodrigo

Na boa, olha a forma que implementei esse problema: (desculpa a falta de identação)
print (“Esse programa lista todos os números primos até o limite que usuário o desejar.n”)

x=int(input(“Até que número deseja que eu teste? “))
#pede ao usuario o valor e converte a string em inteiro

print(“nOs números primos até %s são: ” % x)

for j in range(1, x+1):
# vai usar todos os valores de 1 até o valor x definido pelo usuário

y=1
# Define a variável y como 1 que é o elemento neutro da multiplicação.

for i in range(2, int(j**0.5+1)):
# para cada j ele testa todos os restos possiveis das divisões até dividir pela raiz quadrada + 1.

y=(j%i)*y
# Multiplica todos os restos entre si.

if y>0:
# caso tenha havido qualquer divisão interia, sem resto, a multiplicação terá resultado zero. Se for primo será diferente de zero.

print (j, end= “, “)

# mostra a lista dos que foram primos (produto de restos diferentes de zero).
#O parâmetro end= “, ” serve para não listar um em baixo do outro e coloca virgula e espaço entre os elementos.
Fail

Desde quando o numero 45 ( ou qualquer 1 terminado em 5) é primo? Seu programa esta errado!

Erko Bridee