Parcialito 3 - 2024a - Tema 3

Ejercicio 1

Un número primo es un número natural mayor que 1 que no tiene divisores positivos aparte de 1 y él mismo. En otras palabras, un número primo sólo es divisible por 1 y por sí mismo. En matemáticas se dice que un número es divisible entre otro siempre y cuando su división sea exacta, es decir, el resto sea cero.

1. Implemente una función esPrimo en C que, dado un número entero n, resuelva si ese número es primo o no.

En teoría de números, la factorización de números enteros es la descomposición de un número entero positivo en un producto de números enteros. Un número entero positivo mayor que 1 se lo llama compuesto cuando es el producto de dos o más números enteros mayores que 1, en caso de no serlo se lo llama número primo.

Por ejemplo, 15 es un número compuesto porque 15 = 5 · 3, pero 7 es un número primo porque no se puede descomponer de esta manera. Si uno de los factores es compuesto, a su vez se puede escribir como producto de factores más pequeños, por ejemplo 60 = 20 · 3 = (5 · 4) · 3 = 5 · 3 · 2 · 2.

En matemáticas, el teorema fundamental de la aritmética establece que todo número entero mayor que 1 puede representarse como un único producto de números primos (sin considerar el orden de los factores).

1. Implemente una función siguientePrimo en C que, dado un número entero n, encuentre el siguiente número primo.

2. Implemente el código principal de un programa en C que pida un número al usuario y luego imprima en pantalla su descomposición en números primos. Se sugiere buscar hacerlo de manera ordenada, de menor a mayor número primo. Deben utilizar las funciones anteriormente implementadas.

   Ejemplo de salida del programa:

   Ingrese un número entero positivo: 60
   Descomposición en primos de 60: 2 2 3 5
   

Ejericio 2

La Criba de Eratóstenes es un antiguo algoritmo para encontrar todos los números primos menores a un número natural n dado (límite). Funciona marcando iterativamente los múltiplos de cada número primo a partir de 2 hasta el límite n.

A continuación se tiene un programa que utiliza el algoritmo de la Criba de Erastóstenes, el cual fue ejecutado y pausado en la línea 11 (marcada por la flecha roja). A su vez, se muestra el estado de las variables hasta dicho momento, con la salvedad del arreglo primes, del cual no se tiene información (sus posiciones de memoria se encuentran en ?):

1. Explique en palabras el comportamiento del programa, y responda las siguientes preguntas:

   • ¿Qué tipo de datos existen en el arreglo primes? ¿Qué representan?
   • ¿Es la variable primes de la función main la misma variable primes de sieve_of_eratosthenes?
   • ¿Por qué la función sieve_of_eratosthenes recibe como argumento int* primes? ¿Qué tipo de datos es?
   • ¿Cuánta memoria ocupa el arreglo primes? ¿Y por qué?

2. Completar el estado de la memoria hasta el momento en que se pausó el programa, justo antes de la ejecución de la línea 11. Se debe completar los valores contenidos en el arreglo primes, notar que se tienen los valores de n, p e i al momento de detenerse el programa.