Question

Se quiere obtener los primeros n números primos (por ejemplo, si n = 5 habría que conseguir los primos 2, 3, 5, 7 y 11). diseñar un algoritmo de programación dinámica que resuelva el problema, encontrando una forma de reutilizar los resultados ya conseguidos para calcular los nuevos números primos.

Answer 1

Para encontrar los n primeros números primos mediante programación dinámica, ejecutamos el siguiente algoritmo:

SubProceso bandera <- esPrimo ( num )

Definir bandera, contador como entero

bandera<-1; //es primo

contador<-num-1;

Mientras bandera=1 y contador>1 Hacer

 Si num MOD contador = 0 Entonces

  bandera<-0;

 Fin Si

 contador=contador-1;

Fin Mientras

Fin SubProceso

Proceso n_primeros_primos

Definir n, nums, i como entero;

Escribir "Ingrese n: " Sin Saltar;

Leer n;

nums=1;

i=1;

Mientras i<=n Hacer

 Si esPrimo(nums)=1 Entonces

  Escribir nums;

  i=i+1;

 Fin Si

 nums=nums+1;

Fin Mientras

FinProceso

Para hacer este algoritmo, debes comprender que:

Número Primo: es aquel que solo puede se divide exactamente entre el mismo número y 1. Si se llegara a dividir, sin residuo, entre algún otro número, ya no sería primo.

Programación Dinámica: es aquella en la que utilizas sub programas que te permiten reutilizar código.

Descripción de algoritmo

1. En el proceso principal, llamado n_primeros_primos  vamos recorriendo los números enteros a partir del 1 y vamos analizando cada uno, enviándolo a un subrpoceso.
2. En el subproceso esPrimo, buscamos algún otro divisor del número ingresado nums. Al encontrarlo hacemos que bandera se vuelva 0, que siginifica que no es primo. En ese momento el subproceso termina. En caso de no encontrar otro divisor, bandera retorna 1, que significa que es primo. En imagen adjunta dejo el diagrama de flujo hecho en PSInt