Inicio > Programing > Encontrar mis primeros mil millones de primos (python) II

Encontrar mis primeros mil millones de primos (python) II

nprimos-3

Este es el segundo intento por encontrar mis primeros mil millones de primos y basándome en las fallas obtenidas de mi anterior intento me me ha ocurrido realizar lo siguiente

la idea!

Como me he dado cuenta que mi laptop puede procesar cantidad de 100,000,000 sin problema, entonces porque no procesar bloques de ese mismo tamaño, así que sólo necesitaría procesar 10 bloques de este tipo para lograr encontrar todos los números primos del 2 al 1,000,000,000.

Por lo tanto necesito de una función que me permita encontrar los números primos dado un intervalo [a, b] y la lista de todos los números primos menores a “a”. Esta función la he llamado range_primos(a, b, primes).

Luego necesito dividir el intervalo de [1, 1,000,000,000] en bloques de 100,000,000 e ir llamando a la función range_primos() para ir calculando los números primos correspondientes a cada rango, esto lo realizo con otra función llamada big_range_primes(n).

Al final la lista primos contendrá todos los primos encontrados en el rango inicial.

Creando la función range_primos()

Esto es relativamente simple, ya que voy a usar la función que he usado anteriormente, pero con algunas modificaciones para encontrar los primos en el intervalo [a, b] en lugar de [2, n], quedando la función de la siguiente manera:

def range_primes(star, stop, primes):

    if len(primes) == 0:
        primes = [2]
    
    i = star
    last = 0
    while i <= stop:
        is_prime = True
        sqrt_limit = int(i**(0.5) + 1)
        for prime in primes:
            if i % prime == 0:
                is_prime = False
                break
            if prime >= sqrt_limit: 
                break
        if is_prime:
            primes.append(i)
            # Se imprime el primo encontrado y el avance en porciento
            avance = int(i / float(stop-star) * 70)
            if avance > last:
                print "=",
                sys.stdout.flush()
                last = avance
        i += 2
    print    

Creando la función big_range_primos(n)

Esta función lo que tiene que hacer es dividir el intervalo [2, n] en intervalos de ancho 100,000,000 en caso de que n sea mayor que 100,000,000, de lo contrario se procesa como un sólo intervalo, quedando la función de la siguiente forma:

def big_range_primes(n):

    width = 100000000
    primes = [2]
    if n > width:
        n_ranges = n / width
        n_rest = n % width
        for i in range(n_ranges):
            star = 3 if (i * width) < 3 else i * width + 1
            stop = (i+1) * width
            print i,
            sys.stdout.flush()
            range_primes(star, stop, primes)
        if n_rest > 0:
            star = n_ranges * width + 1
            stop = n_ranges * width + n_rest
            print n_range,
            sys.stdout.flush()
            range_primes(star, stop, primes)
    else:
        print 0,
        sys.stdout.flush()
        range_primes(3, n, primes)

    print
    return primes

Ejecución

Para hacer uso de las funciones anteriores, además contabilizar el tiempo y guardar en un archivo txt la serie completa de números primos encontrados, utilizo las siguientes líneas de código:

    t1 = time.time()
    primes = big_range_primes(1000000000)
    t2 = time.time()
    print "Cantidad de números primos encontrados: ", len(primes)
    print "Tiempo requerido: ", t2-t1, "seg."

    txtprimes = open("mil_millones_de_primos.txt","w")
    for prime in primes:
        txtprimes.write(str(prime))
    txtprimes.close()

Esto parece ir muy bien, el consumo de memoria es aceptable
nprimos-1
Se puede ver que todavía hay buena cantidad de memoria libre y eso que tengo como 20mil pestañas abiertas con el google chrome, también se puede ver que sólo es uno el núcleo que está procesando el script de python, así que esto todavía se podrías paralelizar.

Si lo ejecutara en un equipo con tecnologías Nvidia por ejemplo donde puedo tener 128 núcleos, creo que podría procesar cantidades aún mayores en tiempos del orden de los minutos.

La ejecución se ve algo así
nprimos-2
y el avance es algo lento, por lo que lo voy a dejar ejecutando y a esperar el resultado.

Resultados!

Después de 22,263s (que es algo así como 6 hrs) el programa ha terminado exitosamente logrando obtener mi mayor número primo hasta el momento 990,000,023 y el total de números primos obtenidos fué de 50,847,534 de primos, sim embargo todavía dista de ser del orden de los mil millones.

Así que ahora tengo que modificar nuevamente mis funciones para leer la lista de números primos que ya tengo en el archivo y utilizarla como base para encontrar números primos a partir del 1,000,000,000.

Si te interesa una lista de estos un poco más de 50 millones de números primos puedes descargar el archivo zip que contiene un archivo txt con la lista de primos separados por comas.
mil_millones_de_primos.zip (128.5 MB)

¿Alguien tendrá una lista de números primos más grande que haya logrado generar?

Salu2+

Anuncios
  1. Jhonny
    16 agosto, 2017 en 19:02

    AUNQUE NO ENTIENDO NADA ME ASOMBRA SIENDO ESTUDIANTE DE 10 AÑOS

    • 16 agosto, 2017 en 19:21

      Hola Jhonny

      Bueno, no se como es que llegaste a esta nota acerca de número primos, es un tema de matemáticas, pero sobre de seguridad informática y/o encriptación de datos (puedes buscar en la wikipedia más info!) y para tus 10 años, no quiero aburrirte con definiciones y teoría pero son cosas que se pueden hacer cuando sabre un poco de programación.

      Si te interesa el tema de hacer programas para computadoras te recomiendo visitar la página de alguien que hizo un libro para que niños de 8 años en adelante pueda entenderlo y hacer sus propios juegos ¿te interesa el dato?

      Salu2+

  1. No trackbacks yet.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

PiKon

3D Printing + Raspberry Pi Camera = PiKon Telescope

gvSIG blog

gvSIG project blog

Python Adventures

Welcome to the Jungle!

A %d blogueros les gusta esto: