Resolução do desafio dos números primos
comentada em 06/01/2020 20:35

Como prometido, disse que domingo à noite ia lançar a resolução do desafio do tópico passado (Desafio de fim de semana - Programa que detecte números primos - Tecnologia - Bastter.com). Antes da solução, só queria dizer que já foi muito bom o resultado do desafio pois no tópico original tivemos duas soluções (do @abra e do @ghoul) que não foram feitas em Python mas sim em C# e Ruby e dessa forma agregam mais ainda o conhecimento por aqui e ainda teve uma sugestão bem legal do @ebitda que me fez pensar em ir além da resolução e falar de performance de código. Então vamos lá.

O desafio era criar um programa que recebesse uma lista de números compreendidos entre 0 a 100 e detectasse quais números constantes dessa lista seriam números primos.

Assim, o programa receberia esta lista:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

E teria como saída esta lista:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Há infinitas formas de fazer, inclusive melhores do que a que fiz, mas aqui priorizei a forma mais legível para iniciantes possível, então só iremos usar laços "for" e condicionais. Mais pra frente incrementei a solução com funções para falar de performance do código. 

Sendo assim, para saber quais números dessa lista são primos, eu decidi inicialmente que iria dividir os números pelos próprios números da lista, fixando um e fazendo as divisões, depois fixando o seguinte e fazendo as divisões...

Minha lista começando no 0, eu iria dividir 0 pelo primeiro número da própria lista que também é 0, entretanto não é possível dividir por 0, então eu preciso pular o 0.

Em seguida, pego o 1, como eu pulo o 0, vou dividir 1 por 1 e obter resto 0, mas a iteração para aí porque o próximo quociente é 2 e eu não quero dividir 1 por 2 pois o resto não é 0, e 1 também não é primo.

Pegando o 2, irei iterar sobre a lista original dividindo inicialmente por 1, depois por 2, obtendo resto 0 nas duas ocasiões e parando por aí, dessa forma encontrando nosso primeiro número primo, já que por definição números primos só são divisíveis por 1 e por ele mesmo.

E assim vou varrer toda a lista até o número 100, sendo que quando chegar em 100 eu vou sair dividindo 100 por 1, por 2, por 3...até ter alguma condição de parada que defina que 100 não é primo. 

Traduzindo isso em código, é mais ou menos isso que eu quero fazer:

# Nossa lista inicial
lista_numeros = [x for x in range(101)]

# Vou criar uma segunda lista que irá receber somente os números primos da primeira lista
lista_primos = list()

# Aqui, vou criar uma lista de divisores excluindo o 0 pois não posso dividir por 0
lista_divisores = [x for x in lista_numeros if x != 0]

# Abaixo está a lógica do algoritmo, que é a iteração sobre cada item da lista inicial
# Eu fixo cada número da lista original e vou iterando sobre a lista de divisores realizando a divisão
for number in lista_numeros: 

    # Aqui, criei uma variávei que vai receber a quantidade de divisores que o número tem
    # Se esse valor for igual a 2, o número é primo
    soma_divisores = 0 

    # Abaixo ocorre um segundo laço, que é o responsável por realizar as divisões
    for divisor in lista_divisores:

        # Condicional que verifica se o resto da divisão do número escolhido pelo divisor é 0
        if number % divisor == 0: 

            # Ocorrendo essa condição, há um incremento na quantidade de divisores do número
            soma_divisores += 1
        
        # Condição para parar o laço quando o divisor for maior que o número a ser dividido
        # Ou seja, se eu tou testando o 5 e vou tentar dividir por 6 o laço para
        elif number < divisor:
            break

    # Ao final das iterações, se a soma de divisores for 2 o número é primo
    if soma_divisores == 2: 
        lista_primos.append(number)

# Imprime a lista de números primos
print(lista_primos)

Uma versão sem os comentários:

lista_numeros = [x for x in range(101)]

lista_primos = list()

lista_divisores = [x for x in lista_numeros if x != 0]

for number in lista_numeros: 

    soma_divisores = 0 

    for divisor in lista_divisores:

        if number % divisor == 0: 
            soma_divisores += 1
        
        elif number < divisor:
            break

    if soma_divisores == 2: 
        lista_primos.append(number)

print(lista_primos)

E temos como resultado:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

E eu poderia parar por aqui, pois já obtivemos a nossa resposta. Mas a ideia do @ebitda de falar sobre otimização de algoritmo me inspirou pra ir além da solução. Então senta que lá vem textão.

Vamos mudar um pouco a estrutura do código. Nossa lista agora vai ser definida inicialmente assim:

max_value = 101

lista = [x for x in range(max_value)]

Fiz isso porque vou brincar com listas maiores do que a lista de 0 a 100. 

Agora vou criar uma função e nela vou usar a biblioteca time para calcular em quanto tempo nosso código roda, ou seja, quanto o Python demora para realizar esses cálculos pra gente:

import time

def primeira_versao(lista_numeros):
    """
    Primeira versão da função, sem otimização de algoritmo
    """
    lista_divisores = [x for x in lista_numeros if x != 0]
    
    start_time = time.time()
    lista_primos = list()
    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1
            elif number < divisor:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)
    print(lista_primos)
    print(f'Duração da primeira versão: {time.time() - start_time:.3f}s')

O esqueleto do código é o mesmo mostrado acima, com a diferença das linhas de código abaixo

start_time = time.time()

print(f'Duração da primeira versão: {time.time() - start_time:.3f}s')

O que essas linhas irão fazer é calcular quanto tempo, em segundos arredondando a partir da terceira casa decimal, demora para a função rodar. Então, nosso programa agora está assim:

import time
max_value = 101

lista = [x for x in range(max_value)]

def primeira_versao(lista_numeros):
    """
    Primeira versão da função, sem otimização de algoritmo
    """
    lista_divisores = [x for x in lista_numeros if x != 0]
    
    start_time = time.time()
    lista_primos = list()
    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1
            elif number < divisor:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)
    print(lista_primos)
    print(f'Duração da primeira versão: {time.time() - start_time:.3f}s')

Chamando nossa função agora:

primeira_versao(lista)

A saída no terminal é:

>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> Duração da primeira versão: 0.001s

Ou seja, o programa demorou 0,001 segundo (ou até menos) para rodar. 

Se aumentarmos nossa lista para uma lista contendo os números de 0 a 1000:

max_value = 1001

lista = [x for x in range(max_value)]

A saída será esta:

>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
>>> Duração da primeira versão: 0.122s

Agora demorou 0,122 segundos.

Aumentando ainda mais, para uma lista de números de 0 a 10000:

>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 
...
9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
>>> Duração da primeira versão: 6.509s

Agora demorou 6,509 segundos. 

Vou aumentar o max_value para 20001, tendo a lista um range de 0 a 20.000 (vinte mil). 

max_value = 20001

lista = [x for x in range(max_value)]

O tempo de resposta com esse valor foi de:

>>> Duração da primeira versão: 25.413s

E vou parar por aqui. 

Vejam como pra calcular os números primos em um intervalo grande a primeira versão do algoritmo demora mais de 25 segundos. 

Vou tentar criar uma primeira forma de otimizar nosso algoritmo. O nosso segundo laço for vai parar quando perceber que o número já tiver mais de 2 divisores, o que já o torna não primo. Então vou alterar isto:

    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1
            elif number < divisor:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)

Para isto:

    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1 
            elif number < divisor:
                break
            if soma_divisores > 2:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)

Nossa segunda versão do código vai ser assim:

def segunda_versao(lista_numeros):
    """
    Segunda versão da função, parando o laço se divisores > 2
    """
    lista_divisores = [x for x in lista_numeros if x != 0]
    
    start_time = time.time()
    lista_primos = list()
    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1 
            elif number < divisor:
                break
            if soma_divisores > 2:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)
    print(f'Duração da segunda versão: {time.time() - start_time:.3f}s')

Rodando agora as duas versões do nosso algoritmo, num range de 0 a 20000:

primeira_versao(lista)
segunda_versao(lista)

Os retornos são:

>>> Duração da primeira versão: 24.999s
>>> Duração da segunda versão: 4.991s

Notem como eu diminuí o tempo em 1/5 do tempo original só parando de iterar quando o número de divisores já fosse maior que 2. 

E dá pra otimizar ainda mais. Nossa terceira versão do algoritmo vai filtrar a lista de divisores só adicionando à possível lista de divisores o número 2, o 4 (sem o 4 como divisor a lógica quebra, pois 4 só será dividido por 1 e por 2, tornando-o falsamente primo) e números ímpares, já que números que são divisíveis por pares, exceto o 2, não são primos:

lista_divisores = [x for x in lista_numeros if x == 2 or x == 4 or x % 2 != 0]

Nossa terceira versão do algoritmo será assim:

def terceira_versao(lista_numeros):
    """
    Terceira versão da função, parando quando divisores > 2 e só dividindo por 2, por 4 e por ímpares
    """
    lista_divisores = [x for x in lista_numeros if x == 2 or x == 4 or x % 2 != 0]
    start_time = time.time()
    lista_primos = list()
    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1 
            elif number < divisor:
                break
            if soma_divisores > 2:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)
    print(f'Duração da terceira versão: {time.time() - start_time:.3f}s')

Rodando as 3 funções agora:

primeira_versao(lista)
segunda_versao(lista)
terceira_versao(lista)

Os tempos de resposta são:

>>> Duração da primeira versão: 26.672s
>>> Duração da segunda versão: 4.695s
>>> Duração da terceira versão: 2.566s

Notem agora que eu quase cortei pela metade o tempo de execução da segunda pra terceira versão. Já em comparação à primeira, quase 10x mais rápido.

Fazendo uma última tentativa de otimização, agora tanto a lista original quanto a lista de divisores só terão o número 2, o 4 e números ímpares:

lista_divisores = [x for x in lista_numeros if x == 2 or x == 4 or x % 2 != 0]

lista_numeros = lista_divisores.copy()

A quarta versão será assim:

def quarta_versao(lista_numeros):
    """
    Quarta versão da função, com a lista de divisores = lista de números
    """
    lista_divisores = [x for x in lista_numeros if x == 2 or x == 4 or x % 2 != 0]
    lista_numeros = lista_divisores.copy()

    start_time = time.time()
    lista_primos = list()
    for number in lista_numeros: 
        soma_divisores = 0 
        for divisor in lista_divisores: 
            if number % divisor == 0: 
                soma_divisores += 1 
            elif number < divisor:
                break
            if soma_divisores > 2:
                break
        if soma_divisores == 2: 
            lista_primos.append(number)
    print(f'Duração da quarta versão: {time.time() - start_time:.3f}s')

Rodando as 4 versões agora:

primeira_versao(lista)
segunda_versao(lista)
terceira_versao(lista)
quarta_versao(lista)

Teremos como resposta:

>>> Duração da primeira versão: 24.339s
>>> Duração da segunda versão: 4.656s
>>> Duração da terceira versão: 2.502s
>>> Duração da quarta versão: 2.107s

Notem que agora a mudança não foi tão significativa mas ainda houve uma melhora de performance no algoritmo.  

Enfim, eu poderia buscar mais formas de tornar isso mais rápido (e há várias mas muitas englobam assuntos não vistos ainda) mas vou parar por aqui. A intenção era mostrar tanto a resolução do desafio como demonstrar como muitas vezes podemos melhorar a performance do nosso código, evitando lags desnecessários. 

Espero que tenha sido útil pra alguém a ideia desse desafio e agradeço quem participou mandando soluções.