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.
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.
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.
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.
| 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 |
| 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 | |||
Primalidad de un número
