4.4. Lista de números primos.

En ocasiones no queremos saber si un número es primo o compuesto, sino que necesitamos tener todos los primos hasta cierta cantidad. Lo primero que podemos hacer para resolver esto es recorrer todos los números, probar si son primos con el método anterior e irlos agregando a un arreglo cuando sí cumplan.

Sin embargo, podemos aprovechar que ya tenemos guardados los primos anteriores. Está claro que si un número compuesto divide a otro, también sus factores lo van a dividir. Al tener los primos guardados, sólo tenemos que recorrer el arreglo para ver si alguno divide al número que estamos probando. Si no lo dividen, agregamos este número a nuestra lista y continuamos.


Problema ejemplo


Criptografía

Problema
Mientras el jurado estaba preparando los problemas para el concurso, surgió un inconveniente: era necesario mandar por correo electrónico los problemas. Como es bien conocido, no es confiable mandar archivos por correo, ya que no van encriptados y pueden ser interceptados. Los miembros del comité no quieren que algún participante conozca los problemas antes del inicio del concurso. Por eso, han decidido recurrir a métodos criptográficos para mantener los textos a salvo de lectores no autorizados. El jurado ha creado una nueva forma de encriptar un texto. Todavía no está patentado, así que se mantiene en secreto. Sin embargo, vamos a revelar un dato: el nuevo algoritmo está basado en el trabajo con números primos. En particular, el cálculo del n-ésimo número primo.

Varios miembros del comité han trabajado de forma independiente en programas que realizan dicho cálculo, pero estos programas arrojan resultados distintos. Cada programador está seguro que el suyo funciona correctamente, por lo que el jurado está en un callejón sin salida, y el concurso está a punto de no llevarse a cabo.

Deberás ayudarle al jurado y salvar el concurso. Queremos que escribas un programa que calcule el n-ésimo número primo. Es muy importante que tu código funcione correctamente.

Entrada
La primera línea es un número natural k. Le siguen k números naturales (uno por línea). Los números no son mayores a 15 000.

Salida
Para cada número n deberás imprimir el n-ésimo número primo. Cada número deberá estar en su propia línea.

Solución: Lo más conveniente en este caso es calcular los primeros 15 000 primos y tenerlos guardados en un arreglo para que después podamos acceder rápidamente al que necesitemos.


Código


Las primeras líneas (líneas 1 a 3) son la declaración de variables: la variable i nos va a servir para los ciclos, k es la cantidad de entradas a procesar, en n leemos la entrada actual y el arreglo p es donde están guardados todos los números primos.

En el procedimiento primos (líneas 5 a 20) es donde calculamos y guardamos todos los primos que nos interesan. La variable n indica cuantos primos vamos a calcular. En la línea 6 declaramos las variables locales: i y j son variables para ciclos, l es una variable temporal y t es la cantidad de primos que hemos encontrado. Empezamos en la línea 8 con la inicialización de variables, agregamos el primer primo que es el dos y con esto podemos empezar del tres e irnos sólo con los impares.

Tenemos un ciclo de las líneas 9 a la 19 que termina hasta que la cantidad de primos en el arreglo sea igual a la que estamos buscando. Al inicio del ciclo revisamos entre todos los primos que son menores que la raíz del número si existe alguno que lo divida (líneas 10 a 12). Si no hay algún primo que divida a este número, se cumple la condición de la línea 13 y con esto incrementamos la cantidad de primos que tenemos y agregamos de encontrar (líneas 15 y 16). En la línea 18 nos vamos con el siguiente número impar a analizar.

En las líneas 22 a 30 está la parte principal del programa. Primero la cantidad de casos a procesar (línea 23) y precalculamos todos los primos que vamos a necesitar (línea 24). De las líneas 25 a 29 leemos las entradas a calcular n e imprimimos el n-ésimo primo de la lista.


Caso ejemplo

Entrada: 10
Desarrollo:  3, 2
 5, 2 3
 7, 2 3 5
 9, 2 3 5 7
11, 2 3 5 7
13, 2 3 5 7 11
15, 2 3 5 7 11 13
17, 2 3 5 7 11 13
19, 2 3 5 7 11 13 17
21, 2 3 5 7 11 13 17 19
23, 2 3 5 7 11 13 17 19
25, 2 3 5 7 11 13 17 19 23
27, 2 3 5 7 11 13 17 19 23
29, 2 3 5 7 11 13 17 19 23
Salida: 2 3 5 7 11 13 17 19 23 29


Código en C



Tiempo de ejecución

Lenguaje Fecha Tiempos [s] Memoria [Kb]
Ejecución Mejor Mediana Peor
Pascal 09-Feb-2006 0.046 0.001 0.090 1.962 195
C 03-Feb-2006 0.046 258





© Pier Paolo Guillen Hernandez
World of πer