«Un matemático, como un pintor o un poeta, es un fabricante de modelos. Si sus modelos son más duraderos que los de estos últimos, es debido a que están hechos de ideas. Los modelos del matemático, como los del pintor o los del poeta deben ser hermosos. La belleza es la primera prueba; no hay lugar permanente en el mundo para unas matemáticas feas»
– Godfrey Harold Hardy (1877-1947)
INTRODUCCIÓN
Un método clásico para encontrar Números Primos, inculcado en las aulas académicas a nivel de bachillerato en la Materia de Matemáticas es la Criba de Eratóstenes, que consiste en un algoritmo que permite hallar a los Números Primos menores a un número natural “n”.
Los Números Primos son entidades matemáticas de suma importancia, pues son los ladrillos de los números naturales, es decir, cualquier número natural compuesto, puede descomponerse como multiplicación de Números Primos, por ejemplo 33 = 3*11. Desde tiempos antiquísimos, estos Números han fascinado a los matemáticos de todas las razas, pues el orden de su distribución aun sigue siendo un misterio, en la actualidad, las entidades primales se usan en la seguridad informática, por ejemplo, en el algoritmo RSA que se basa en ellos para codificar transacciones digitales.
Algoritmo de Eratóstenes2
Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos, el método comienza con el 2, se tachan todos sus múltiplos; luego se comienza de nuevo, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado Primo, y se procede a tachar todos sus múltiplos, y así sucesivamente el proceso termina cuando el cuadrado del mayor número confirmado como primo no lo es, tal como se aprecia en la imagen I.
El Autor de la criba para Números Primos fue Eratóstenes3, quien nació en Cyrene (Libia) en el año 276 a. C., trabajó en diversos campos como la astronomía, la historia, la literatura y las matemáticas. Estudió en Alejandría y Atenas, y alrededor del año 255 a. C fue el tercer director de la Biblioteca de Alejandría. Una de sus principales contribuciones a la ciencia y a la astronomía fue su trabajo sobre la medición de la Tierra.
El Método Alternativo
Comenzaremos diciendo que este método, tiene la capacidad de cribar a los Números Primos mayores o iguales a cinco, enunciamos los pasos de la siguiente manera, y recalcamos que hace uso de las funciones 6n+1 y 6n-1:
- Elegimos hasta que número natural queremos realizar una búsqueda de Números Primos, al número seleccionado le llamaremos cota superior “b”, de tal manera que el intervalo de búsqueda estará comprendido en 5<=X<=b.
- A la cota superior “b” calculada en el paso 1), la dividiremos entre seis y al resultado obtenido le aplicamos un redondeo al entero inmediato(n=b/6), al número obtenido lo representaremos con “n”.
- Dibujaremos una tabla que contendrá tres columnas principales, en la primer columna realizamos la tabla de multiplicar del 6 hasta “n”, (valor obtenido en el paso dos), en la segunda columna para cada resultado de la primer columna restamos la unidad y en la tercer columna para cada resultado de la primer columna sumamos la unidad.
Los Pivotes serán valores de la columna dos y tres que al multiplicarse por si mismo y por los sucesivos números de las columnas en donde se encuentran, deben arrojar valores que también están contenidos en las susodichas columnas, los cuales hay que tachar, cuando los productos de los pivotes arrojen valores que ya no se encuentran en sus columnas, los valores que no hayan quedado sin tachar serán Números Primos.
Un Ejemplo
- Encontrar Números Primos hasta el Número 100, (El intervalo se fija en 5<=X<=100).
- n=b/6 = 100/6 =16.66…=17.
- Tabla
Los Pivotes son 5 y 7, y los resultados a tachar de la tabla en base a las multiplicaciones efectuadas son los siguientes:
En el siguiente apartado, agregamos el código del ejemplo de este algoritmo, para su ejecución en el programa denominado Wolfram Mathematica, en donde hacemos uso de la notación de Conjuntos.
Ejemplo de Código en Wolfram Mathematica para este Ejemplo |
AA = Table[6n + 1, {n, 1, 17}];BB = Table[6n – 1, {n, 1, 17}] CC = Union[AA, BB]; DD = 5*Union[AA, BB]; EE = 7*Union[AA, BB]; PRIMOS=Complement[CC, DD, EE] |
CONCLUSIONES
- El Método expuesto en el presente material puede servir como apoyo en la Materia de Matemáticas a la hora de estudiar a los Números Primos.
- Encontrar Números Primos a través del algoritmo expuesto, es una tarea aún más simple que la Criba de Eratóstenes, pues su mejora radica en el hecho de no explorar a todos lo Números que se encuentran en el rango establecido.
- El algoritmo presentado puede enseñarse de manera paralela al de la Criba de Eratóstenes en las Aulas Académicas, permitiendo diversificar los caminos para encontrar Números Primos en un determinado intervalo.
- Es posible programar en algún lenguaje de programación este algoritmo y así poder cribar a los Números Primos de manera automatizada.
- Como ventaja tenemos que los tiempos se reducen en relación a la Criba de Eratóstenes.
- La posible desventaja sería que, entre mayor sea la cota superior del intervalo, más pivotes se han de utilizar y las multiplicaciones aumentan en este algoritmo de búsqueda Primal.
Comentar que hemos incorporado esta criba a nuestra página web mejorando sensiblemente los tiempos de procesamiento respecto al anterior algoritmo usado, basado en la original criba de Eratóstenes.
Tiene la ventaja tambien, ademas de las comentadas en el artículo, favorecer el procesamiento en multitarea con la asociación de pivotes a las tareas.
Permite también una sencilla adaptación a la compartición del espacio para un calculo independiente de primalidad por tramos,de manera que por ejemplo con un mapa de bits contenido en un fichero de 1.000.000.000 bytes siendo
cada bit un bit con información de primalidad para cada numero en este rango ,se puede calcular tramos de 1 Peta byte, y así cubrir el espacio de 10^15 a 10^18 de una manera razonable con un ordenador personal.
Una vez analizado un tramo , esto nos permite acceder a cualquier numero del tramo en un tiempo inferior al minuto desde la web siempre utilizando el algoritmo de esta optimización.
Finalmente nos queda no obstante conocer si esta mejora tiene alguna denominación específica y el autor , si este está registrado, sino es el propio autor del articulo.
n=int(input(‘n: ‘))
múltiplos=set()
print(2,end=’ ‘)
for i in range (3,n+1,2):
If i not un múltiplos:
print(i,end=’ ‘)
múltiplos.update(i,N+1,i)
##algoritmo Python, corto, rápido
y sin complicaciones##