Free Palestine and Lebanon 🍉 Stop the Genocide
Haskell Logo

Programação Funcional

Questão 21: isPrime

Voltar

Apresente uma definição recursiva da função isPrime :: Int -> Bool que dado um número inteiro maior ou igual a 2 determina se esse número é primo. Para determinar se um número n é primo, descubra se existe algum número inteiro m tal que 2 ≤ m ≤ √n e mod n m = 0. Se um tal número não existir então n é primo, e se existir então n não é primo.

Exemplo

> isPrime 7
True
> isPrime 21
False

Resolução

Clica para revelar

isPrime :: Int -> Bool
isPrime n = n >= 2 && primeCheck n 2

primeCheck :: Int -> Int -> Bool
primeCheck n m
    | m * m > n = True
    | mod n m == 0 = False
    | otherwise = primeCheck n (m + 1)

Explicação

Clica para revelar

Esta questão é um bocado complicada de definir, porque precisamos de verificar várias condições para vários números. Como tal, a melhor forma de a definir é recorrendo a uma função auxiliar.

O nosso objetivo aqui é percorrer todos os números entre 2 e √n e verificar se o valor dado é divisível por algum destes números. Se tal acontecer, o valor não é um número primo. Caso contrário, é primo.

Vamos então definir a nossa função principal:

isPrime :: Int -> Bool
isPrime n
    | n >= 2 = primeCheck n 2
    | otherwise = False

Aqui, primeCheck será a função auxiliar, na qual n é o valor de input e m é o acumulador, isto é, o valor que vai começar em 2 e acabar em √n. Damos a m o valor 2 como valor inicial.

Sendo assim, a nossa função auxiliar irá percorrer os valores inteiros entre 2 e √n. Podemos definir algo deste género:

primeCheck :: Int -> Int -> Bool
primeCheck n m
    | m >n = ???
    | otherwise = ???

Como estamos a percorrer os valores por ordem crescente, o caso de paragem ocorrerá quando m atingir um valor superior a √n.

Em Haskell, os valores reais (como raizes quadradas) são diferentes dos valores inteiros, por isso, se estivermos a trabalhar com variáveis destes dois tipos, precisamos de as converter para o mesmo tipo. Para evitar estes problemas, podemos simplificar m > √n para m * m > n, elevando os dois lados da inequação ao quadrado.

A nossa condição para um número não ser primo é ser divisível por m. Em Haskell, isso traduz-se em mod n m == 0, ou seja, a divisão de n por m dá resto (mod) nulo. Podemos então acrescentar essa condição à nossa função:

primeCheck :: Int -> Int -> Bool
primeCheck n m
    | m * m > n = ???
    | mod n m == 0 = False
    | otherwise = ???

Assim, se a condição falhar para qualquer valor, sabemos que n não é primo. Sendo assim, também sabemos que, se atingirmos o caso de paragem, significa que n não é divisível por nenhum valor entre 2 e √n, logo será primo.

primeCheck :: Int -> Int -> Bool
primeCheck n m
    | m * m > n = True
    | mod n m == 0 = False
    | otherwise = ???

No otherwise, precisamos apenas de definir a “recursão”, isto é, se as condições de cima falharem, devemos verificar para o valor de m seguinte.

primeCheck :: Int -> Int -> Bool
primeCheck n m
    | m * m > n = True
    | mod n m == 0 = False
    | otherwise = primeCheck n (m + 1)