Problema 1.20

Neste problema é-nos pedido um programa que teste se um dado inteiro é primo. Um número diz-se primo se os únicos divisores são ele próprio e o número 1. Este exemplo dá-nos a oportunidade de mostrar como as definições nos permitem usar a abstracção e estruturar o código. Na nossa abordagem começamos com a definição:

def primo(n):
    conta = divisores_c(n)
    if conta == 2:
        return True
    else:
        return False

Como se vê pela solução apresentada (linha 2) delegamos noutra definição, divisores_c(n), a contagem dos divisores. Se esse número for 2 será primo, caso contrário não será. Claro que o programa estará correcto apenas se forem incluídos 1 e o próprio número na contagem, como na solução seguinte.

def divisores_c(n):
    """
    Conta os divisores de um número.
    """
    conta = 0
    for i in range(1, n+1):
        if (n % i) == 0:
            conta = conta + 1
    return conta

Esta solução baseia-se no uso do padrão acumulador. O acumulador do resultado conta é inicializado na linha 5 e actualizado na linha 8. Visualmente temos a seguinte dependência entre as duas definições:





Mas admitamos que queremos optimizar o programa que conta os divisores deixando de fora o caso óbvio dos divisores próprios. Podemos então optar por:

def divisores_c(n):
    """
    Conta os divisores de um número.
    """
    conta = 0
    for i in range(2, n/2 + 1):
        if (n % i) == 0:
            conta = conta + 1
    return conta

Só precisámos mexer na linha 6 do código! Agora necessitamos alterar o nosso programa principal.

def primo(n):
    conta = divisores_c(n)
    if conta == 0:
        return True
    else:
        return False

E já está!