[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección2.4Ejercicios de Programación

1La Criba de Eratóstenes

Un método para calcular todos los números primos menores a un cierto entero positivo dado \(N\) es listar todos los números \(n\) tales que \(1 \lt n \lt N\text{.}\) Comience eleminando todos los múltiplos de 2. Después elimine todos los múltiplos de 3. Ahora elimine todos los múltiplos de 5. Note que 4 ya ha sido eliminado. Continúe de esta manera, notando que no es necesario llegar hasta \(N\text{;}\) es suficiente con parar en \(\sqrt{N}\text{.}\) Usando este método, calcule todos los números primos menores a \(N = 250\text{.}\) También podemos usar este método para encontrar todos los enteros que son relativamente primos a un entero \(N\text{.}\) Simplemente elimine los factores primos de \(N\) y todos sus múltiplos. Usando este método, encuentre todos los números que son relativamente primos con \(N= 120\text{.}\) Usando la Criba de Eratóstenes, escriba un programa que calcule todos los primos menores que un entero \(N\text{.}\)

2

Sea \({\mathbb N}^0 = {\mathbb N} \cup \{ 0 \}\text{.}\) La función de Ackermann es la función \(A :{\mathbb N}^0 \times {\mathbb N}^0 \rightarrow {\mathbb N}^0\) definida por las ecuaciones

\begin{align*} A(0, y) & = y + 1,\\ A(x + 1, 0) & = A(x, 1),\\ A(x + 1, y + 1) & = A(x, A(x + 1, y)). \end{align*}

Use esta definición para calcular \(A(3, 1)\text{.}\) Escriba un programa para evaluar la función de Ackermann. Modifique el programa para que cuente el número de comandos ejecutados en el programa cuando se evalúa la función de Ackermann. ¿Cuántos comandos se ejecutan en la evaluación de \(A(4, 1)\text{?}\) ¿\(A(5, 1)\text{?}\)

3

Escriba un programa que implemente el algoritmo de Euclides. El programa debiese aceptar dos enteros positivos \(a\) y \(b\) como entrada y la salida debiese ser tanto \(\gcd( a,b)\) como enteros \(r\) y \(s\) tales que

\begin{equation*} \gcd( a,b) = ra + sb. \end{equation*}