EXERCÍCIO PROGRAMA 1

Data de entrega: 18/9/2001

Problema. Escreva um programa para a máquina TOY que imprime todos os números primos menores ou iguais a um dado inteiro n.

1. O seu programa deve ser “eficiente”, no sentido que o número de ciclos (ou instruções) que a máquina TOY executa até terminar deve ser o menor possível, especialmente para valores de n grandes.

Seja inventivo! Use qualquer ferramenta que você conhecer para escrever este programa. Aqueles que escreverem os programas mais eficientes vão ganhar um prêmio! (Isto é, além da nota.)

2. Entregue um relatório descrevendo o funcionamento do seu programa.

3. Seja f(n) o número de instruções que seu programa executa para imprimir todos os primos ≤ n. Inclua em seu relatório uma tabela com valores de f(n).

4. Inclua também em seu relatório uma “estimativa” para a sua função f(n). Para obter esta estimativa, você pode usar métodos “experimentais” (extrapolando os dados de sua tabela de f(n)) ou teóricos (usando, entre outros, estimativas para o número de números primos ≤ n).