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 numbersdefprime(n):#Set first two primes
print('2 ,3 ,', end = '')
for i in range(5,n):
primo=Truefor j in range(2 , i//2):
if i%j == 0:
primo=Falsebreakelse:
passif primo == True:
print('{} ,'.format(i), end = '')
#Prime numbers Dinamic programmingdefprime_dinamic(n):#Set first two primes
print('2 ,3 ,', end = '')
primes=[2,3]
for i in range(5,n):
primo=Truefor j in primes:
if i/2 < j:
breakif i%j == 0:
primo=Falsebreakelse:
passif 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:
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!!
¡Saludos! que buen aporte, aquí vengo a realizar el mio, optimizando más aún el sistema, basándonos en el hecho que no existe un primo mayor a la raíz del número que lo divida; y no en el hecho de que no existe un primo mayor a la mitad del número como se plantea en este programa, así generando una lista de primos que ya no se crea de forma lineal, si no de forma exponencial (^(1/2)), y puesto que este ultimo acorta exponencialmente la lista de verificación, optimiza aun mas el sistema. aquí dejo el código, y la correspondiente comparación hallando los primeros 100000, donde la diferencias es de 7.76 s contra 0.23 s.
from time import time #Prime numbers Dinamic programmingdefprime_dinamic(n):#Set first two primes#print('2 ,3 ,', end = '') primes=[2,3] for i in range(5,n): primo=Truefor j in primes: if i/2 < j: breakif i%j == 0: primo=Falsebreakelse: passif primo == True: #print('{} ,'.format(i), end = '')#Save in memory the new prime primes.append(i) return primes defprimos_dinamicos(n):#input int n: Número Limite#output list primos: Lista de números primos hasta n primos = [2,3] for numero in range(5, n): es_primo = True sqrtnum = numero**0.5for primo in primos: if sqrtnum < primo: breakif numero % primo == 0: es_primo = Falsebreakelse: passif es_primo == True: primos.append(numero) return primos defmain():#Set number n = int(input('What is the value of n?: ')) print('for n={}'.format(n)) #lineal#time's counter start [s] start=time() #Call prime lista1 = prime_dinamic(n) #time's counter end [s] end=time() #Result print() print('Dinamic_lineal in {}[s]'.format(end-start)) #print(lista1)#sqrt#time's counter start [s] start=time() #Call prime lista2 = primos_dinamicos(n) #time's counter end [s] end=time() #Result print() #print(lista2) print('Dinamic_sqrt in {}[s]'.format(end-start)) print(lista1 == lista2) if __name__ == '__main__': main()El True que se lee a lo ultimo, es verificando que las listas generadas por ambos sistemas sean iguales.
What is the valueof n?: 100000for n=100000 Dinamic_lineal in7.760688066482544[s] Dinamic_sqrt in0.23821115493774414[s] TrueNúmeros primos hasta 1 M:
What is the valuefor n?: 1000000for n=1000000 Dinamic_lineal in3.8969268798828125[s] Dinamic_sqrt in524.9841587543488[s] TrueUfff amigo ese aporte estuvo brutal!!! esa no me la sabía!!!
Ya lo probe y deja en la lona mi planteamiento y por mucho! si no te molesta lo voy a agregar al notebook de este trabajo -> https://colab.research.google.com/drive/1mlPaAjA02XSE65oIvpn-yZL-8cTA4JWT
Gracias y saludos!!!
Excelente!
Gracias!!!
link al código -> https://colab.research.google.com/drive/1mlPaAjA02XSE65oIvpn-yZL-8cTA4JWT
podrías pasar el link del código???