Generando números primos gemelos

Continuando con los posts sobre números (en especial los primos), les presento los números primos gemelos. Como recordarán, escribí un posteo donde creabamos un algoritmo para detectar números primos. En base a eso vamos a hacer una pequeña modificación para este post.

¿Qué son los primos gemelos?

Como sabrán, los únicos números primos que son consecutivos son el 2 y el 3, y como todos los primos sacando el dos son impares, entonces podemos tomar como “consecutivos” los números con diferencia de 2. Entonces llamamos números primos gemelos a p y q si p es primo y q es primo siendo q=p+2

Por ejemplo, 3 y 5 son primos gemelos.

Propiedades de los primos gemelos

-A partir del par (5, 7), el número intermedio es siempre múltiplo de 6, por ende de 2 y de 3.

-La suma de los inversos de los primos gemelos converge a una constante llamada “Constante de Brun”.

-n y n+2 son primos gemelos si y solo si:

Vamos a programar esto

Bueno, basados en el código que teníamos para ver si un número es primo podemos hacer un rango para que busque pares de primos gemelos:

from datetime import *

def esPrimo(numero):
    primo=True
    if numero>3:
        if numero%2!=0 and numero%5!=0:
            for i in range(3,(numero-1)/2,2):
                if numero%i==0:
                    primo=False
                    break
        else:
            if numero==5:
                primo=True
            else:
                primo=False
    else:
        if numero<2:
            primo=False
        else:
            primo=True
    return primo        

desde= raw_input("Ingrese Desde: ")
hasta= raw_input("Ingrese Hasta: ")
print datetime.today()
for i in range(int(desde),int(hasta)+1):
    if esPrimo(i)==True:
        if esPrimo(i+2)==True:
            print "("+str(i)+","+str(i+2)+")"
print datetime.today()

En este caso, veamos cuanto tarda en registrar los pares desde 1000000 hasta el número 1005000.

Los resultados son los siguientes:

2013-07-31 16:51:18.665000
(1000037,1000039)
(1000211,1000213)
(1000289,1000291)
(1000427,1000429)
(1000577,1000579)
(1000619,1000621)
(1000667,1000669)
(1000721,1000723)
(1000847,1000849)
(1000859,1000861)
(1000919,1000921)
(1001087,1001089)
(1001321,1001323)
(1001387,1001389)
(1001549,1001551)
(1001807,1001809)
(1001981,1001983)
(1002149,1002151)
(1002257,1002259)
(1002341,1002343)
(1002347,1002349)
(1002359,1002361)
(1002719,1002721)
(1002767,1002769)
(1002851,1002853)
(1002929,1002931)
(1003001,1003003)
(1003109,1003111)
(1003199,1003201)
(1003349,1003351)
(1003361,1003363)
(1003367,1003369)
(1003619,1003621)
(1003817,1003819)
(1003907,1003909)
(1004117,1004119)
(1004657,1004659)
(1004669,1004671)
(1004747,1004749)
2013-07-31 16:51:33.455000

Lo que vemos es que tarda en hacer todo esto la friolera de 15.210 segundos (descartemos una parte que es de impresión, pero no importa, sigamos).

Ahora vamos a tratar de mejorar esto un poco, sabemos por las propiedades que vimos que los números intermedios son divisibles por 6 (si y solo si n>5).

Agreguemosle esas condiciones. Entonces no debe buscar un primo más.

from datetime import *

def esPrimo(numero):
    primo=True
    if numero>3:
        if numero%2!=0 and numero%5!=0:
            for i in range(3,(numero-1)/2,2):
                if numero%i==0:
                    primo=False
                    break
        else:
            if numero==5:
                primo=True
            else:
                primo=False
    else:
        if numero<2:
            primo=False
        else:
            primo=True
    return primo        

desde= raw_input("Ingrese Desde: ")
hasta= raw_input("Ingrese Hasta: ")
print datetime.today()
for i in range(int(desde),int(hasta)+1):
    if esPrimo(i)==True:
        if i<=5 or (i+1)%6==0:  
            if esPrimo(i+2)==True:
                print "("+str(i)+","+str(i+2)+")"
print datetime.today()

Pero ahora los tiempos son:

2013-07-31 16:57:07.142000

2013-07-31 16:57:21.129000

Entonces bajamos el tiempo a poco menos de 14 segundos (13.987). Ok, no le ganamos tanto (1.223 segundos), pero supongo yo que en números grandes la diferencia que se puede marcar es superior.

Bueno, supongo que en el próximo capítulo tendremos que ocuparnos un poco de este señor Brun