Subtarefa

Implemente um predicado em Prolog para gerar números primos segundo o algoritmo designado por Crivo de Eratóstenes. Esse método permite-nos construir uma lista de todos os primos até um limite dado, de acordo com a seguinte descrição3:

``Escrevemos os naturais desde 2 até ao limite desejado; por exemplo 200:

\begin{displaymath}2,\,3,\,4,\,5,\,6,\,7,\,\ldots ,\,198,\,199,\,200\mbox{.} \end{displaymath}

Começando no princípio da lista, o primeiro número que encontramos é 2, um primo. Deixamos 2 de lado, e passamos à frente marcando os números de 2 em 2, isto é, marcamos 4, 6, 8, 10, $\cdots $. Depois de ter marcado todos os números pares até 200, voltamos ao princípio da lista para encontrar o primeiro número depois de 2 que não foi marcado: é 3. Deixamos 3 de lado (é primo), e passamos à frente marcando os números de 3 em 3: marcamos 6, 9, 12, 15, $\cdots $. Prosseguimos assim. Depois de fazermos este jogo repetidamente para 2, 3, $\ldots $, N, onde N é o maior natural não marcado tal que $N\le \sqrt{200}$, então os números da lista que ainda não foram marcados são os primos até 2002.''


Delfim F. Marado Torres
1998-06-16