Usar programación dinámica para buscar números primos

Otro problema donde se puede utilizar la programación dinámica es buscando números primos muy grandes ej. “Cuales son números primos entre 0 y 200,000”
*Dato un número primo (n) es aquel que solo puede ser dividido entre 1 y el mismo número (n) teniendo como residuo un número entero
En la práctica esto significa ir dividiendo el número (n) desde 2 hasta n/2 para comprobar los residuos de cada división, haciéndolo de forma recursiva el problema es exponencial porque conforme más avanzas tienes que comprobar todos estas operaciones previas.

Sin embargo utilizando un poco de matemáticas y lógica se puede llegar a la conclusión de que un número es primo siempre y cuando al dividir este entre los números primos anteriores a n/2 el cociente no sea un número entero

ej. 23 es un número primo?

En vez de hacer las 10 comprobaciones previas desde 2 hasta n/2=23/2~11 -> [2-11]
Solo se hacen 4 comprobaciones -> [3,5,7,11]
resultando que si, 23 es un número primo

En programación dinámica esto qué significa?
Significa ir guardando en un arreglo todos los números primos que se vayan encontrando, para usarlos en las futuras operaciones matemáticas

código:

from time import time
 
#Prime numbers
def prime(n):
   #Set first two primes
   print('2 ,3 ,', end = '')
 
   for i in range(5,n):
       primo=True
       for j in range(2 , i//2):
           if i%j == 0:
               primo=False
               break
           else:
               pass
       if primo == True:
           print('{} ,'.format(i), end = '')
          
#Prime numbers Dinamic programming
def prime_dinamic(n):
   #Set first two primes
   print('2 ,3 ,', end = '')
   primes=[2,3]
  
   for i in range(5,n):
       primo=True
       for j in primes:
           if i/2 < j:
               break
           if i%j == 0:
               primo=False
               break
           else:
               pass
       if primo == True:
           print('{} ,'.format(i), end = '')
           #Save in memory the new prime
           primes.append(i)
 
#Set number
n=200000
print('for n={}'.format(n))
 
#Recursive
#time's counter start [s]
start=time()
#Call prime
prime(n)
#time's counter end [s]
end=time()
#Result
print()
print('Recursive in {}[s]'.format(end-start))
 
#Dinamic
#time's counter start [s]
start=time()
#Call prime
prime_dinamic(n)
#time's counter end [s]
end=time()
#Result
print()
print('Dinamic   in {}[s]'.format(end-start))

El resultado de esto es:

El link del codigo ->

Como se puede observar el tiempo de procesamiento se reduce de forma muy considerable.
Esta es otra prueba de cómo la programación dinámica ayuda al tiempo de procesamiento.

Saludos!!