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
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
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)