6

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 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:
Screenshot from 2020-04-14 11-22-49.png

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!!

Escribe tu comentario
+ 2
Ordenar por:
3
13089Puntos

¡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]
True
4
13089Puntos
2 años

Números primos hasta 1 M:

What is the valuefor n?: 1000000for n=1000000

Dinamic_lineal in3.8969268798828125[s]

Dinamic_sqrt   in524.9841587543488[s]
True

1
11011Puntos

podrías pasar el link del código???