Cálculo de números primos


Partindo de algumas leituras sobre as regras de números primos, então acabei por criar um pequeno script que gera os números primos de 1 até um limite informado, da forma mais pythônica que consegui.

def eh_primo(numero):
    #Verifica se um numero eh primo ou nao
    return True if sum([ 1 for div in range(2,numero) if numero % div == 0 ]) == 0 else False

def primos(limite):
    #Numeros primos
    numeros = [2] + range(3,limite+1,2)
    primos = []
    for num in numeros:
        if sum([ 1 for div in range(2,num) if num % div == 0 ]) == 0 :
            primos.append(num)
    return primos
    
print primos(100)
print primos(500)
print eh_primo(18)
print eh_primo(19)
print eh_primo(20)
print eh_primo(23)

Explicando:
– Números primos são somente números ímpares e o 2
– Não valida com 1 e o próprio número, pois não necessita
– cria uma lista com o 2 e a partir do 3, somente os ímpares
– verifica se a SOMA dos 1 retornados para cada NÚMERO onde o resto da divisão (%) entre o NÚMERO e cada um dos menores que ele for igual a zero, quer dizer que o número é divisível por outro número além de 1 e ele mesmo.

Olha, não é fácil entender a primeira vista este trecho de código, mas consegui finalmente chegar até um pequeno script sem muitos loops, graças as facilidades do python, com sua List Comprehension e Programação Funcional !

Conseguem melhorar ainda mais este script ?

Anúncios

4 Comments

  1. Vai depender do que seja ‘melhorar ainda mais’. Para a resolução do problema 10 do Projeto Euler que deseja saber a soma dos números primos em uma determinada faixa, esse programa é impraticável para o valor proposto (2.000.000).

    Testa o tempo para a soma atribuindo 100.000 (que está longe de 2.000.000)
    print sum(primos(100000))

    Otimizar para velocidade implica em seguir outro caminho no algoritmo.

    Curtir

    Responder

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s