Inicio > Programing > Encontrando mi primer millón de números primos (python)

Encontrando mi primer millón de números primos (python)

find_primes_01

Parece que esto de los números primos es algo que crea adicción y según recuerdo es la tercera ves que me pasa con estos número, pero ahora tengo herramientas que años atrás no tenía.

Me he encontrado con que hay algunos concursos para quien encuentre números primos realmente gigantes, estamos hablando de números primos que tienen del orden de 17 millones de cifras sólo para darse una idea.

Pero como todo en la vida hay que comenzar con dando pasitos y luego ya corremos, aunque puede que intente correr un poco, ya veremos cuantas caídas aguanto!!!

Encontrando todos los número primos en el rango de 2 a 1,000,000

Mi primer reto es encontrar todos los número primos en el rango de 2 a 1,000,000 y para ello voy a crear la fundición find_primes() en python y luce más o menos así:

def find_primes(limit):
    primes = [2]
    i = 3
    while i <= limit:
        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)
            print ".",
        i += 2
    print
    return primes

Con esta función he encontrado los todos los números primos en este rango en unos cuantos segundos con un total de 78498 si los últimos 5 son [999953, 999959, 999961, 999979, 999983]

Entonces como esto ha sido muy rápido ahora con el segundo reto…

Encontrando todos los número primos en el rango de 2 a 10,000,000

Bueno, simplemente uso la misma función y espero… cabe mencionar que mi laptop es Core i3 de segunda generación por lo que tengo 4 nucleos para procesar, pero en lo que escribo esto el programa ha terminado…

...
3 9999469 9999481 9999511 9999533 9999593 9999601 9999637 9999653 9999659 9999667 9999677 9999713 9999739 9999749 9999761 9999823 9999863 9999877 9999883 9999889 9999901 9999907 9999929 9999931 9999937 9999943 9999971 9999973 9999991

In [5]: len(primes)
Out[5]: 664579

Así que esto está siendo muy rápido y todavía no obtengo mi primer millón de primos, así que es hora del siguiente reto…

Encontrando todos los número primos en el rango de 2 a 100,000,000

Esto ya debería de tardar un poco más, así que desde ya comienzo… y después de varios varios minutos, pero no más de una hr tengo el resultado, haré modificaciones al código para obtener el tiempo de ejecución de aquí en adelante…

...
9999401 99999437 99999439 99999481 99999509 99999517 99999539 99999541 99999547 99999551 99999563 99999587 99999589 99999611 99999617 99999623 99999643 99999677 99999703 99999721 99999773 99999787 99999821 99999827 99999839 99999847 99999931 99999941 99999959 99999971 99999989

In [7]: primes = find_primes.find_primes(100000000)
KeyboardInterrupt

In [7]: len(primes)
Out[7]: 5761455

In [8]: primes[-5:]
Out[8]: [99999931, 99999941, 99999959, 99999971, 99999989]

In [9]: 

Estupendo, ya tengo mi primer millón de primo, o mejor dicho mis 5,761,455 primos

Por cierto para determinar si un número es o no primo, lo que hago es verificar si el número en turno es divisible entre alguno de los factores primos desde 2 hasta sqrt(n), además que de para n sólo considero números impares ya que por obvias razones todos los pares no son primos.

Esto ha resultado en un algoritmo muy eficiente, desde mi punto de vista, sin embargo al leer un poco, me encuentro con que estoy en el rango de los llamado muy pequeños números primos, osea números que tienen menos de 100 dígitos. Ops!

Pero es un comienzo!!!

Salu2+

About these ads
Categorías:Programing Etiquetas: , ,
  1. Victor Luis
    25 septiembre, 2013 en 04:10 | #1

    Me parece bien, yo busco en rangos de 50.000.000 tengo una Pentium-III y me tarda unos minutos. Lo unico de malo que veo en tu Metodo es que cuando llegues a 500.000.000 veras que el proceso se vuelve lento, no tanto por tu equipo, sino por el metodo que aplicas.
    Para buscar nuevos numeros primos, cada vez tendras que evaluar una gran cantidad de veces y para esto necesitas todos los primos que vayas obteniendo, tendrias te tener Gigas y Gigas para ir almacenando y aun asi el proceso sera lento cada vez.

    Cambia de metodo, es mi sugerencia, lo hice tambien, como el metodo PRI-BASE te da solo posibles primos, ya descartados mas del 65-70% de no primos, de modo que la evaluacion es menor en cantidad y tiempo. Otro detalle es que mientras mas grande el rango de busqueda, el tiempo de proceso va disminuyendo con este metodo, lo contrario al metodo que aplicas.

    Piensalo, replantea y buscaras de forma efectiva numeros primos gigantes….

    Atte. Victor Luis Arteaga viluar22 @ hotmail.com

    • 25 septiembre, 2013 en 20:06 | #2

      Hola Victor!

      Este comentario tuyo me será de mucha ayuda, me voy a poner manos a la obra y efectivamente son muy ciertas tus observaciones, el orden de tiempo que estoy tardando crece de manera lineal cuando menos, pero como bien mencionas ya con ordenes de 500,000,000 ya se consumen muchos recurso.

      Buscaré el método de PRI-BASE que mencionas y ya posteo algo!

      Por cierto y tú en que lenguaje trabajas?

      Un gustazo y gracias por el tiempo en dedicarte que comentar!
      Felices búsquedas!
      RT

  2. Victor Luis
    10 diciembre, 2013 en 02:49 | #3

    Holas…

    El programa lo realice en Visual Basic pues tengo bases suficientes en este; pero no creo que sea de lenguaje de programacion, sino del metodo aplicado.

    Revisa esta pagina
    http://primos-origen.es.tl/SERIE-PROGRESIVA—k1-%2B2-k2–k1-%2B4-k2-.htm

    ○ Con este metodo de serie progresiva, creas una base de numeros reducidos a casi la mitad, donde estan los numeros primos y tambien numeros compuestos o no primos. Usando los primos encontrados depuras estos no primos de forma directa como indica el metodo. Para lo cual podrias hacer lo siguiente:

    ○ Cargas en un vector los numeros base, iniciando desde 5 y usando la serie progresiva. Por ejemplo, vp es el vector y lo cargas usando un bucle For-Next

    Erase vp
    np=0
    For g=5 To 10000 Step 6
    vp(np+1)=g
    np=np+2
    vp(np)= g+2
    Next g

    ○ Ahora Depuras los no primos, usando los primos del vector y tomando el ultimo numero base de vp:

    upp= vp(np)
    For g=1 To np
    Select case vp(g)
    Case Is > 0
    pp= vp(g) ‘ pp sera la variable que tiene el numero primo
    ‘.. Aqui es Primo porque no fue depurado como multiplo
    ‘..
    ‘..
    End select

    Next g

    ○ Calculas la posicion del 1º multiplos, donde para todos es PP * 5, estando en [8]=25 donde np1=8 que es la posicion del primer multiplo de grupo.
    ○ A partir de esta posicion comenzara la depuracion de sus multiplos, para lo cual previamente calculas NS y NM2:

    ns = Round(((pp*2)/3), 0)
    nm2= pp * 2

    ○ Inicias un bucle que vaya depurando sus multiplos:

    For h=np1 To np Step nm2
    vp(h)=0
    vp(h+ns)=0
    Next h

    Lo que hacemos es borrar los multiplos en el vector, donde al final solo quedaran los numeros primos.

    ○ Para saber donde terminar la depuracion, sacas la raiz cuadrada del ultimo numero base y si el primo es mayor a este, sales del bucle, pues no habra mas multiplos.

    ○ Finalmente exportas o archivas los numeros primos, usando un bucle que recorra el vector, donde seran primos los que sean mayores a 0:

    For g=1 To np
    Select case vp(g)
    Case Is >0
    ‘–> Es PRIMO… lo muestras en un ListBox o lo archivas

    End select

    Next g

    MsgBox “BUSQUEDA TERMINADA.”

    ◘ Sencillo verdad..? pero ese metodo lo deje pues es todavia lento y desarrolle el Metodo PRI-BASE donde los numeros base son mas seleccionados ya que se obtienen de los “Primos Origen”.
    ◘ Hasta ese entonces, solo habia identificado a los primos origen; pero habia cometido un error en la programacion, donde cuando estaba llegando a los 3 billones hice una revision y habian muchos no primos… revise el metodo y encontre la falla, estaba en un calculo y no lo controlaba. Revise los primos encontrados anteriormente y estaban plagados de no primos.
    ◘ Esto me motivo a realizar un mejor analisis, donde encontre la “secuencia de multiplos directos” con lo que sabia que multiplos depurar en los numeros base y perfeccione el calculo para determinar la posicion de los multiplos, con los que se forma los datos secuencia (DS), por lo que ahora era mas rapido y eficiente.
    ◘ Luego de haber encontrado esa secuencia, para no perder el hilo, hice otros analisis donde descubri otras secuencias que relacionan directamente a los primos origen y los primos originados de estos, con lo que puedo demostrar, que de estos se originan todos los numeros primos, que no aparecen al azar, siendo lo contrario, ya que las secuencias aplicadas a las propiedades de cada primo origen, es lo que determina la aparicion y/o posicionamiento de todos los numeros primos.

    ► Mi proximo proyecto es, desarrollar un programa para buscar numeros primos, donde solo use los primos origen, ya que estos tienen toda la informacion que se transmite a los numeros primos que se originan de cada uno.

    Suerte y sigue adelante….

    Atte. viluarte22 @ hotmail.com

  3. Victor Luis
    11 diciembre, 2013 en 13:01 | #5

    Holas …

    Esa noticia es un reto tecnologico global, donde los Servicios de Internet deben estar super contentos, pues estaran horas y horas conectados a la nube para buscar primos perdidos; pero se podrian encontrar grandes logros…

    Pero, no indican como será el proceso…¿la nube usa tu equipo o solo necesita la coneccion a internet ? ¿Donde se guardan o quedan los posibles primos encontrados? ó ¿la nube te da el servicio de una super computadora para lo uses y busques primos? ya que te ofrecen 200$ gratis de inicio… en fin, ojala que se logren cosas buenas.

    En este pagina

    http://ireneses.wordpress.com/2013/06/02/modelos-probabilisticos-de-la-distribucion-de-numeros-primos-el-proceso-de-bertrand/

    me han dado buenos consejos y me aventurare a lo imposible, crear un metodo que genere numeros primos, directamente… haber que resulta… luego te lo comento… y cuando publique mi metodo PRI-BASE te lo hare saber… OK

  4. 9 febrero, 2014 en 22:09 | #6

    Esto facilitaria tu calculo, antes de aplicar tu algoritmo, debes de descartar los NUMEROS QUE NUNCA SERAN PRIMOS YA SEA PAR O IMPAR, y a su vez detecta automaticamente un NUMERO PRIMO

    Este procedimiento detecta 100% todo los numeros primos, con el sencillo defecto que tambien detecta numeros divisibles por numeros primos, pero de igual manera descarta automaticamente el 75% de los numeros.

    Ejemplo de numeros que detecta una simple formula que desarrolle.

    101 Numero Primo Puro
    103 Numero Primo Puro
    107 Numero Primo Puro
    109 Numero Primo Puro
    113 Numero Primo Puro
    121 Numero Primo Puro
    127 Numero Primo Puro
    131 Numero Primo Puro
    137 Numero Primo Puro
    139 Numero Primo Puro
    143 Numero Primo Puro
    149 Numero Primo Puro
    151 Numero Primo Puro
    157 Numero Primo Puro
    163 Numero Primo Puro
    167 Numero Primo Puro
    169 Numero Primo Puro
    173 Numero Primo Puro
    179 Numero Primo Puro
    181 Numero Primo Puro
    187 Numero Primo Puro
    191 Numero Primo Puro
    193 Numero Primo Puro
    197 Numero Primo Puro
    199 Numero Primo Puro
    209 Numero Primo Puro
    211 Numero Primo Puro
    221 Numero Primo Puro
    223 Numero Primo Puro
    227 Numero Primo Puro
    229 Numero Primo Complejo
    233 Numero Primo Puro
    239 Numero Primo Puro
    241 Numero Primo Puro
    247 Numero Primo Puro
    251 Numero Primo Puro
    253 Numero Primo Puro
    257 Numero Primo Puro
    263 Numero Primo Puro
    269 Numero Primo Puro
    271 Numero Primo Puro
    277 Numero Primo Puro
    281 Numero Primo Puro
    283 Numero Primo Puro
    289 Numero Primo Puro
    293 Numero Primo Puro
    299 Numero Primo Puro
    307 Numero Primo Complejo
    311 Numero Primo Puro
    313 Numero Primo Puro
    317 Numero Primo Puro
    319 Numero Primo Puro
    323 Numero Primo Puro
    331 Numero Primo Puro
    337 Numero Primo Complejo
    341 Numero Primo Puro
    347 Numero Primo Complejo
    349 Numero Primo Puro
    353 Numero Primo Puro
    359 Numero Primo Puro
    361 Numero Primo Puro
    367 Numero Primo Puro
    373 Numero Primo Puro
    377 Numero Primo Puro
    379 Numero Primo Complejo
    383 Numero Primo Puro
    389 Numero Primo Complejo
    391 Numero Primo Puro
    397 Numero Primo Puro
    401 Numero Primo Puro
    403 Numero Primo Puro
    407 Numero Primo Complejo
    409 Numero Primo Complejo
    419 Numero Primo Puro
    421 Numero Primo Puro
    431 Numero Primo Complejo
    433 Numero Primo Puro
    437 Numero Primo Puro
    439 Numero Primo Puro
    443 Numero Primo Puro
    449 Numero Primo Complejo
    451 Numero Primo Puro
    457 Numero Primo Puro
    461 Numero Primo Complejo
    463 Numero Primo Puro
    467 Numero Primo Puro
    473 Numero Primo Puro
    479 Numero Primo Complejo
    481 Numero Primo Puro
    487 Numero Primo Puro
    491 Numero Primo Complejo
    493 Numero Primo Complejo
    499 Numero Primo Puro
    503 Numero Primo Puro
    509 Numero Primo Puro
    517 Numero Primo Puro
    521 Numero Primo Puro
    523 Numero Primo Complejo
    527 Numero Primo Puro
    529 Numero Primo Puro
    533 Numero Primo Puro
    541 Numero Primo Complejo
    547 Numero Primo Puro
    551 Numero Primo Puro
    557 Numero Primo Puro
    559 Numero Primo Puro
    563 Numero Primo Complejo
    569 Numero Primo Puro
    571 Numero Primo Complejo
    577 Numero Primo Puro
    583 Numero Primo Puro
    587 Numero Primo Complejo
    589 Numero Primo Puro
    593 Numero Primo Puro
    599 Numero Primo Puro
    601 Numero Primo Complejo
    607 Numero Primo Puro
    611 Numero Primo Puro
    613 Numero Primo Complejo
    617 Numero Primo Complejo
    619 Numero Primo Complejo
    629 Numero Primo Puro
    631 Numero Primo Puro
    641 Numero Primo Complejo
    643 Numero Primo Puro
    647 Numero Primo Complejo
    649 Numero Primo Puro
    653 Numero Primo Puro
    659 Numero Primo Puro
    661 Numero Primo Puro
    667 Numero Primo Complejo
    671 Numero Primo Puro
    673 Numero Primo Complejo
    677 Numero Primo Puro
    683 Numero Primo Puro
    689 Numero Primo Puro
    691 Numero Primo Puro
    697 Numero Primo Complejo
    701 Numero Primo Puro
    703 Numero Primo Puro
    709 Numero Primo Puro
    713 Numero Primo Complejo
    719 Numero Primo Puro
    727 Numero Primo Puro
    731 Numero Primo Puro
    733 Numero Primo Puro
    737 Numero Primo Complejo
    739 Numero Primo Puro
    743 Numero Primo Puro
    751 Numero Primo Puro
    757 Numero Primo Complejo
    761 Numero Primo Complejo
    767 Numero Primo Puro
    769 Numero Primo Puro
    773 Numero Primo Puro
    779 Numero Primo Complejo
    781 Numero Primo Puro
    787 Numero Primo Complejo
    793 Numero Primo Puro
    797 Numero Primo Complejo
    799 Numero Primo Puro
    803 Numero Primo Complejo
    809 Numero Primo Puro
    811 Numero Primo Puro
    817 Numero Primo Complejo
    821 Numero Primo Puro
    823 Numero Primo Complejo
    827 Numero Primo Puro
    829 Numero Primo Puro
    839 Numero Primo Puro
    841 Numero Primo Puro
    851 Numero Primo Puro
    853 Numero Primo Complejo
    857 Numero Primo Puro
    859 Numero Primo Puro
    863 Numero Primo Complejo
    869 Numero Primo Complejo
    871 Numero Primo Puro
    877 Numero Primo Complejo
    881 Numero Primo Puro
    883 Numero Primo Complejo
    887 Numero Primo Complejo
    893 Numero Primo Puro
    899 Numero Primo Puro
    901 Numero Primo Complejo
    907 Numero Primo Puro
    911 Numero Primo Puro
    913 Numero Primo Puro
    919 Numero Primo Puro
    923 Numero Primo Puro
    929 Numero Primo Complejo
    937 Numero Primo Complejo
    941 Numero Primo Puro
    943 Numero Primo Puro
    947 Numero Primo Puro
    949 Numero Primo Puro
    953 Numero Primo Complejo
    961 Numero Primo Complejo
    967 Numero Primo Puro
    971 Numero Primo Puro
    977 Numero Primo Puro
    979 Numero Primo Puro
    983 Numero Primo Complejo
    989 Numero Primo Complejo
    991 Numero Primo Complejo
    997 Numero Primo Puro
    911 Numero Primo Puro
    913 Numero Primo Complejo
    919 Numero Primo Puro
    923 Numero Primo Complejo
    929 Numero Primo Puro
    937 Numero Primo Puro
    941 Numero Primo Puro
    943 Numero Primo Complejo
    947 Numero Primo Puro
    949 Numero Primo Complejo
    953 Numero Primo Puro
    961 Numero Primo Complejo
    967 Numero Primo Puro
    971 Numero Primo Puro
    977 Numero Primo Puro
    979 Numero Primo Complejo
    983 Numero Primo Puro
    989 Numero Primo Complejo
    991 Numero Primo Puro
    997 Numero Primo Puro

    • 10 febrero, 2014 en 01:47 | #7

      Hola Fabian!

      Bueno en mi método lo que hago es iniciar un arreglo con el “2″ y verifico si el número es divisible entre 2, si lo es lo descarto inmediatamente, así que todos los pares quedan fuera.

      Si no es divisible entre “2″, entonces el siguiente número en la lista es “3″, verifico si es divisible entre “3″, así descarto todos los que son divisibles entre “3″ y así sucesivamente.

      Sin embargo bien tienes razón, yo voy barriendo toda la lista desde el 2 hasta el límite superior que yo indique, entonces tu propones crear una lista intermedia que tendría aproximadamente el 35% del tamaño que la que yo estoy usando.

      Tengo algunas preguntas:
      ¿Cuánto tarda tu método en obtener la lista reducida si consideras analizar todos los números enteros desde el 2 hasta el 100,000,000?
      ¿Cuánto para obtener la lista reducida desde el 2 hasta 1,000,000,000?
      ¿cuánto para obtener la lista desde 2 hasta 1,000,000,000,000?

      Otras más:
      ¿A que llamas un número primo puro?
      ¿A que llamas un número primo complejo?

      Salu2+

  1. 11 febrero, 2013 en 13:42 | #1

Deja un comentario

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

MeXcel Plus

Compartiendo e Intercambiando Conocimiento

Bicicletas Antiguas México

Somos un grupo de ciudades sin fines de lucro y con el único interés de revitalizar las viejas bicicletas antiguas en la ciudad de México

Proyecto greenBE

Reverdece metrópolis

Hacking life, in life

Luis/chajaro/toño/qualen

De pensamientos al texto

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 800 seguidores

%d personas les gusta esto: