← Volver a los ejercicios

Test de primalidad: exists negado, forall y el rango sin elementos

Un número n es primo si n >= 2 y ningún entero entre 2 y n - 1 lo divide. Las dos versiones escriben esa condición de maneras distintas: una niega que exista un divisor, la otra pide que ninguno divida. Elija un valor de n, prediga cuántos divisores alcanza a probar la búsqueda y avance paso a paso. Los valores disponibles son los del main, donde la corrida con la versión de Scala del proyecto del curso da (0 to 12).filter(esPrimo) igual a Vector(2, 3, 5, 7, 11).

1. Las dos versiones y el valor de n

La guarda y la búsqueda van en líneas separadas para que cada una lleve su propio contador. Es la misma expresión que el archivo de el código del tema la escribe en una sola línea.

¿Cuántos divisores alcanza a probar la búsqueda antes de responder?

2. La búsqueda, paso a paso

paso 0 de 0
esPrimoExists(n) devuelve –
esPrimoForall(n) devuelve –
■ líneas 2 y 6: la guarda n >= 2 ■ línea 3: un paso por cada divisor que prueba exists ■ línea 7: los mismos divisores con la condición de forall

Cuando el rango no tiene elementos, la línea de la búsqueda se visita una vez y el contador de divisores probados se queda en cero. Cuando la guarda falla, el && no llega a evaluar la búsqueda y esa línea no se visita.

3. Los divisores que se probaron

Una fila por divisor. Las dos últimas columnas son las condiciones de las dos versiones sobre ese mismo divisor.

4. Las dos condiciones son contrarias

En ninguna fila de la tabla las dos últimas columnas dicen lo mismo: donde n % d == 0 es true, n % d != 0 es false. Esa es toda la diferencia entre las dos versiones.

exists se detiene en el primer divisor que cumple su condición y responde true; la negación de delante lo convierte en false. forall se detiene en el primero que falla la suya, que es ese mismo divisor, y responde false. Las dos paran en el mismo sitio, prueban los mismos divisores y entregan el mismo valor, y eso es lo que se ve en el main: las dos columnas coinciden en los trece números de 0 a 12.

5. El rango sin elementos

Cinco preguntas sobre el caso que decide si la guarda hace falta. Cada opción equivocada dice en qué consiste la confusión.

6. Lo que se lleva de aquí

El && evalúa su lado derecho solo si el izquierdo es true. Con n = 0 y n = 1 la guarda es falsa y la búsqueda no corre: el contador de la línea 3 se queda en cero y la función responde false sin mirar ningún divisor.

La guarda no está ahí para eso, sino para un caso más fino. Si se quitara, con n = 1 quedaría el rango 2 until 1, que no tiene ningún elemento, y forall sobre una colección sin elementos devuelve true: el 1 pasaría por primo. Lo mismo con exists, que devolvería false y la negación lo volvería true. El rango sin elementos deja pasar las dos versiones, y n >= 2 es lo único que lo descarta.

Ese mismo rango sin elementos es el que hace primo al 2 con todo derecho: 2 until 2 no tiene divisores que probar, y un número mayor o igual que 2 al que no se le encuentra divisor es primo. La guarda lo deja pasar y la búsqueda no prueba nada, que es el caso en que los contadores se quedan en cero con una respuesta afirmativa.

Lo que cuesta cada respuesta también se ve en los contadores. Sobre un compuesto la búsqueda se detiene en el primer divisor, y con n = 9 eso son dos pruebas. Sobre un primo no hay dónde detenerse y el rango se recorre entero: n = 11 pide nueve. Para un mismo n, responder que es primo cuesta el rango completo y responder que no lo es cuesta solo hasta el primer divisor.