Questão 3: Escreva uma função em Haskell, sem o uso direto de recursão, que receba um número e retorne True se o número for primo, e False caso contrário.

Passo 1

O enunciado pede uma função em Haskell que receba um inteiro e retorne True se ele for primo, sem usar recursão direta. Precisaremos de técnicas de programação funcional como listas por compreensão ou funções de ordem superior (any ou all) e de um método para testar divisores até √n.

Passo 2

Primeiro, identificamos o caso-base: números menores que 2 não são primos. Então, se n < 2, retornamos False imediatamente.
Em seguida, para n ≥ 2, geramos a lista de possíveis divisores de n, que vai de 2 até floor (√n). Para isso usamos [2 … floor (sqrt (fromIntegral n))].

Passo 3

Para testar primalidade, basta verificar se existe algum divisor d nessa lista tal que n mod d == 0. Se existir, o número não é primo.
Em Haskell, podemos usar any (\n -> condição) lista, que retorna True se ao menos um elemento satisfizer a condição. Como queremos saber se não há divisores, usamos not (any …).
Finalmente, montamos a função isPrime combinando o caso-base e o teste com any, tudo sem nenhum padrão recursivo explícito.

Resposta

isPrime :: Int -> Bool
isPrime n
| n < 2 = False
| otherwise = not (any (\d -> n mod d == 0) [2 … floor (sqrt (fromIntegral n))])

Exercícios relacionados