Exercícios 2.4 Exercícios de Programação
1. A Crivo de Eratóstenes.
Um método para calcular todos os números primos menores do que um certo inteiro positivo dado \(N\) é listar todos os números \(n\) tais que \(1 \lt n \lt N\text{.}\) Comece eliminando todos os múltiplos de 2. Depois elimine todos os múltiplos de 3. Agora elimine todos os múltiplos de 5. Note que 4 já foi eliminado. Continue desta maneira, notando que não é necessário chegar até \(N\text{;}\) é suficiente parar no \(\sqrt{N}\text{.}\) Usando este método, calcule todos os números primos menores do que \(N = 250\text{.}\) Também podemos usar este método para encontrar todos os inteiros que são relativamente primos a um inteiro \(N\text{.}\) Simplesmente elimine os fatores primos de \(N\) e todos seus múltiplos. Usando este método, encontre todos os números que são relativamente primos com \(N= 120\text{.}\) Usando a Crivo de Eratóstenes, escreva um programa que calcule todos os primos menores do que um inteiro \(N\text{.}\)
2.
Seja \({\mathbb N}^0 = {\mathbb N} \cup \{ 0 \}\text{.}\) A função de Ackermann é a função \(A :{\mathbb N}^0 \times {\mathbb N}^0 \rightarrow {\mathbb N}^0\) definida pelas equações
Use esta definição para calcular \(A(3, 1)\text{.}\) Escreve um programa para avaliar a função de Ackermann. Modifique o programa para que conta o número de comandos executados no programa quando se avalia a função de Ackermann. Quantos comandos se executam na avaliação de \(A(4, 1)\text{?}\) \(A(5, 1)\text{?}\)
3.
Escreve um programa que implemente o algoritmo de Euclides. O programa deve aceitar os inteiros positivos \(a\) e \(b\) como entrada e a saída deve ser tanto \(\gcd( a,b)\) como inteiros \(r\) e \(s\) tais que