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+

Anuncios