Averiguar si un número es primo usando fórmula

Hay varias formas de averiguar si un número es o no primo en Excel usando tan sólo funciones de hoja de cálculo (es decir, sin recurrir a VBA), pero en esta pequeña monografía expondré tan sólo fórmulas desarrolladas por mí. Con esto no estoy diciendo que yo sea el único que puede desarrollarlas (lo que sería una tontería por mi parte porque cualquiera que se tome el tiempo necesario podría hacerlo), sino que yo las he desarrollado por mí mismo.

Viene esto a cuento porque estoy un poco cansado de ver cómo después de publicar alguna fórmula en la página destinada a ello de este sitio web, poco tiempo después y "sin duda por casualidad" aparece en otros sitios, "naturalmente" sin citar al autor.

Vayan por delante mis dudas de que Excel sea la herramienta idónea para averiguar si un número es o no primo, y además la utilidad para la mayoría de nosotros de averiguarlo es prácticamente nula. Pero para mí intentar "exprimir" las posibilidades de Excel es una especie de pasatiempo, y el reto de conseguir una fórmula capaz de averiguar si un número tan grande como la precisión numérica máxima de esta aplicación informática es o no primo ha sido siempre algo que me ha parecido desafiante.

Hay que tener en cuenta que todas las fórmulas de esta página son matriciales, por lo que hay que introducirlas pulsando mayúsculas control entrada al mismo tiempo. Las llaves { } no hay que incluirlas, deberían aparecer automáticamente al introducir la fórmula como matricial. Las pongo en las fórmulas porque son una convención mayoritariamente aceptada para indicar que una fórmula es matricial.

Los puntos y comas de las fórmulas podrían tener que ser sustituidos por comas: esto dependerá del separador de listas que esté establecido en la configuración regional del equipo.

Presentaré cuatro fórmulas, cada una capaz de procesar un número más grande que la anterior, empezando por una capaz de procesar hasta el 1.099.513.724.928 (en Excel 2010) y terminando por otra que puede llegar a procesar un número tan grande como la precisión numérica máxima de Excel (999.999.999.999.999):

En esta gráfica se representa el límite (en Excel 2010) de cada una de las cuatro fórmulas que veremos en este trabajo.

Sabemos que hay infinitos números primos (http://es.wikipedia.org/wiki/Teorema_de_Euclides), pero el límite al que se puede llegar en Excel para determinar si uno dado es primo o compuesto utilizando funciones de hoja de cálculo dista mucho no ya, lógicamente, de esa infinitud sino incluso de números realmente grandes. Este límite, en Excel, está determinado por tres factores: uno subjetivo y otros dos objetivos.

El factor subjetivo, lógicamente, depende de cada persona y del rendimiento de su computadora, porque estas fórmulas pueden requerir varios segundos si han de procesar números grandes, y no todos los usuarios ven con agrado tener que esperar unos segundos a que una fórmula devuelva un resultado.

El primero de los dos factores objetivos es la precisión numérica máxima de Excel (artículo sobre el tema), la cual sabemos que es de 15 dígitos. Esto significa que el entero más alto que puede procesar Excel mediante el uso de funciones de hoja de cálculo para averiguar si es primo o compuesto es el 999.999.999.999.999, y nada hay que se pueda hacer para superarlo.

El segundo factor objetivo es la cantidad de memoria de acceso aleatorio (RAM) de la computadora. Hay que tener en cuenta que algunas fórmulas requieren la creación de matrices de datos realmente grandes si el número a procesar también lo es, hasta el punto de que podría llegar a aparecer el mensaje "Excel se ha quedado sin recursos", que (en este contexto) indicaría que la aplicación no es capaz de generar las matrices requeridas por la fórmula, al no disponer el equipo informático de memoria física disponible suficiente para ello.

En la página cuyo enlace he puesto más arriba, concretamente aquí, muestro una fórmula capaz de procesar hasta el 4.295.098.367 en Excel 2003 y hasta el 1.099.513.724.928 en las versiones posteriores. La fórmula es:

{=SUMA(--(MULTIPLO.INFERIOR(A1;FILA(INDIRECTO("1:"&ENTERO(RAIZ(A1)))))=A1))=1}

y devolverá el valor lógico VERDADERO si el número situado en A1 es primo, y FALSO en caso contrario.

El funcionamiento de esta fórmula es bastante sencillo: crea una matriz desde 1 hasta la raíz cuadrada del número situado en A1 (que se supone es el que se desea procesar), tras lo cual aplica la función MULTIPLO.INFERIOR a cada uno de los elementos de la matriz. Para saber qué es lo que hace exactamente esta función de hoja de cálculo aconsejo una consulta a la ayuda de Excel sobre ella.

Si el número es compuesto, más de un elemento de la matriz lo contendrá, mientras que si es primo tan sólo lo contendrá un elemento. Los dos signos negativos se encargan de convertir en unos y ceros los valores lógicos generados al resolver la igualdad:

Ya sólo queda sumar esos unos y ceros, comprobar si dicha suma es o no 1 y devolver VERDADERO o FALSO dependiendo de esta condición.

El límite superior de esta fórmula, que ya expuse antes, está determinado por esta otra:

¿Se podría mejorar la fórmula anterior para aumentar el límite de números que puede procesar? Veamos. Tal como ya he dicho, la fórmula genera una matriz desde 1 hasta la raíz cuadrada del número a procesar. Salta a la vista que en esa matriz todos los elementos que contienen un número par (excepto el 2, que sí es primo) resultan innecesarios puesto que cualquier número par >2 es divisible por 2 y, por lo tanto, es imposible que sea primo. Es algo que ya sabemos, y no necesitamos que MULTIPLO.INFERIOR nos lo confirme.

Así pues, resulta evidente que si encontrásemos una forma de generar esa misma matriz pero tan sólo con los números impares estaríamos duplicando de hecho su capacidad. La expresión capaz de hacer esto es:

Al estar constituida esta nueva matriz tan sólo por números impares, habrá que tener la precaución de añadir una expresión a la fórmula capaz de determinar si el número es par. La forma más sencilla de hacer esto, sobre todo en Excel 2010, es utilizar la función ES.PAR. Esta función se encuentra disponible también en las versiones anteriores, pero para poder utilizarla es necesario activar el complemento 'Herramientas para análisis' (desde Herramientas->Complementos).

{=SI(ES.PAR(A1);FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;FILA(INDIRECTO("1:"&ENTERO(REDONDEAR.MAS(RAIZ(A1);0)/2)+1))*2-1)=A1))=1)}

Hay que tener en cuenta que la fórmula fallará para el 2 y el 3 (dirá que no son primos cuando obviamente lo son). Esto se podría solucionar añadiéndole más SIes, pero pienso que sería complicarla innecesariamente porque supongo que cualquier persona que esté leyendo esto sabe que el 2 y el 3 son números primos...

¿Cuáles son los límites de esta nueva fórmula? Bien, sabemos ya que el límite inferior es el 4. El límite superior está determinado por la fórmula:

que devuelve 4.398.042.316.801 para Excel 2007 y 2010 y 17.179.607.041 para Excel 2003.

Respecto a esta segunda fórmula, cabe subrayar el hecho de que al no tener que procesar los números pares no sólo se duplica la capacidad de la matriz, sino que además los cálculos se reducen a la mitad con respecto a los requeridos para procesar el mismo número usando la primera fórmula, con lo que la velocidad de proceso con respecto a ella debería ser prácticamente el doble.

Hemos visto cómo con la fórmula anterior ha sido posible prácticamente cuadruplicar el número más alto que se puede procesar, al prescindir de la necesidad de calcular los números pares, es decir los terminados en 2, 4, 6, 8 y 0. ¿Sería posible prescindir de alguna otra terminación?

Lo cierto es que sí, puesto que sabemos que todos los números terminados en 5 son divisibles por 5 (los terminados en cero también, pero estos ya quedaban eliminados con la fórmula anterior), así que si pudiésemos evitar los cálculos de dichos números terminados en 5 (los cuales, obviamente, no pueden ser nunca primos a excepción del propio 5) ahorraríamos un 20% del tiempo de proceso de esta segunda fórmula e incrementaríamos su capacidad.

El problema es cómo "decirle" a la fórmula que no incluya esta terminación. Hay que considerar que la forma de eliminar los números pares en la segunda fórmula se basaba en el hecho de que cualquier número impar puede ser escrito como 2n - 1, siendo n un número entero (http://es.wikipedia.org/wiki/Números_pares_e_impares). Pero, hasta donde yo sé, no hay una forma tan sencilla como esa de "obligar" a la fórmula a crear tan sólo los elementos correspondientes a los enteros acabados en 1, 3, 7 y 9.

La solución que me parece más cómoda pasa por el uso de una matriz bidimensional, es decir, con más de una columna; en concreto, cuatro columnas: una para cada una de las posibles terminaciones 1, 3, 7 y 9. El problema es que para la creación de esta matriz tendremos que utilizar literales de matriz (también denominados a veces "constantes matriciales"), y la creación de este tipo de datos en Excel requiere el uso de los separadores de filas y/o columnas en literales de matriz que estén establecidos en la configuración regional del equipo.

Por ejemplo, en la configuración regional de mi portátil (la que viene por defecto en Windows 7 Home Premium 64 bit como "Español (España)"), el separador de columnas para los literales de matriz es la barra invertida \ y el separador de filas el punto y coma, así que estos son los separadores que usaré en las siguientes fórmulas. Pero reitero que en otras configuraciones regionales podrían ser otros distintos.

Por fortuna, no resulta demasiado complicado conseguir que el propio Excel nos diga cuales son esos separadores, sin necesidad de entrar en las opciones de configuración regional del equipo. Basta con ejecutar el siguiente código VBA:

Public Sub MostrarSeparadoresDeMatriz()
    'Este procedimiento muestra un msgbox informando de cuales son los separadores para los literales de matriz.
    With Application
        MsgBox "El separador de columnas para los literales de matriz es " & .International(xlColumnSeparator) _
        & vbNewLine & vbNewLine & "El separador de filas para los literales de matriz es " _
        & .International(xlRowSeparator), vbOKOnly
    End With
End Sub

Una cosa a tener en cuenta con respecto a los literales de matriz es que sus llaves {} sí han de ser tecleadas, al contrario que las que aparecen al principio y al final de las fórmulas matriciales, que son puestas automáticamente por Excel.

Vimos en la primera fórmula que la misma creaba la serie completa de números desde el 1 hasta la raíz cuadrada del número a procesar. En la segunda fórmula, la serie era la de los números impares desde el 1 hasta la raíz cuadrada del número a procesar. Como lo que estamos intentando conseguir ahora es una matriz que contenga tan sólo los enteros terminados en 1, 3, 7 y 9, las (por poner un ejemplo) cuatro primeras filas de la matriz bidimensional deberían ser:

... y así hasta llegar a la raíz cuadrada del número a procesar dividida entre 10. El porqué de esta división entre 10 lo veremos enseguida.

Si nos fijamos en la serie, es fácil percatarse de que, a partir de su segunda fila, cada elemento es el resultado de sumarle 10 al elemento situado en la misma columna de la fila anterior.

Así pues, si como primera fila utilizamos el literal de matriz {1\3\7\9} no resulta difícil construir la matriz que necesitamos mediante el sencillo método de sumarle a este literal de matriz el resultado de multiplicar por 10 la fila correspondiente. Es más difícil intentar explicarlo que ver la expresión necesaria para la creación de esta matriz:

El uso de la función REDONDEAR.MAS viene determinado por la necesidad de garantizar que la matriz llegue hasta la raíz cuadrada del número que se está procesando (no pasa nada si se supera pero podría pasar si no se llegase), algo que podría no suceder de usarse ENTERO.

Por ejemplo, si ponemos en A1 cualquier entero entre 901 y 1600 la matriz generada por la fórmula será exactamente las cuatro primeras filas que vimos antes.

Una vez conseguida esta matriz, el proceso es el mismo que el seguido con las dos fórmulas anteriores: aplicarle a cada uno de sus elementos la función MULTIPLO.INFERIOR, comparar los resultados con el número que se está procesando, convertir los valores lógicos en ceros y unos, y sumarlos. La fórmula, por lo tanto, será:

{=SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/10;0)))-1)*10)=A1))=1}

El motivo por el que dividimos por 10 la raíz cuadrada del número a procesar a la hora de calcular las filas que deberá tener la matriz es que en esa fila de la matriz ya se alcanza la mencionada raíz cuadrada del número. Por ejemplo el 1231: su raíz cuadrada es 35,0856 y si le aplicásemos la función REDONDEAR.MAS sin haber dividido antes entre 10 pasaría a ser 36. Pero si creásemos la matriz con esas 36 filas, dicha matriz alcanzaría el número 359, algo completamente innecesario puesto que al 36 ya se llega en la fila 4 de la matriz, como puede comprobarse en el listado de las cuatro primeras filas que vimos más arriba.

1) Si se intentan procesar los primos 2, 3, 5 ó 7, la fórmula dirá que no lo son (nótese que se trata de los cuatro números primos de la primera decena).

3) La fórmula dirá que son primos los números acabados en 5 que sólo sean divisibles por 5.

El primer problema lo podemos resolver creando un nuevo literal de matriz que contenga esos cuatro números primos y buscando en él el número que se está procesando, usando la función COINCIDIR:

{=SI(ESNUMERO(COINCIDIR(A1;{2\3\5\7};0));VERDADERO;SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/10;0)))-1)*10)=A1))=1)}

La función ESNUMERO se utiliza para procesar el error #N/A que producirá COINCIDIR si no encuentra el número en el literal de matriz {2\3\5\7}.

{=SI(ESNUMERO(COINCIDIR(A1;{2\3\5\7};0));VERDADERO;SI(ES.PAR(A1);FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/10;0)))-1)*10)=A1))=1))}

Y el tercer problema se puede solucionar añadiendo un nuevo SI para verificar que el número no termina en 5. Así que la fórmula final, provisionalmente, sería:

{=SI(ESNUMERO(COINCIDIR(A1;{2\3\5\7};0));VERDADERO;SI(ES.PAR(A1);FALSO;SI(DERECHA(A1;1)="5";FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/10;0)))-1)*10)=A1))=1)))}

En esta fórmula, los SIes están dispuestos de forma que tengan que ser evaluados antes de llegar a la expresión que construye la matriz, así que tan sólo se llegará a crearla si el número que se está procesando ha pasado los "filtros" previos, que no requieren mucho cálculo.

El problema de esta forma de meter SIes dentro de SIes es que se van añadiendo niveles de anidamiento, hasta tal punto que la fórmula no podría ser utilizada en versiones de Excel anteriores a la 2007, ya que genera 8 niveles de anidamiento cuando el máximo permitido en esas versiones es 7.

Hay (al menos) una forma de reconvertir esta fórmula a otra que sí pueda ser utilizada en Excel 2003 (lo cual, lógicamente, implica que también podria usarse en las versiones posteriores):

{=SI(ESNUMERO(COINCIDIR(A1;{2;3;5;7};0));VERDADERO;SI(SUMA(--(RESIDUO(A1;{2;3;5;7})=0))>0;FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/10;0)))-1)*10)=A1))=1))}

Pero surge un nuevo problema: estamos utilizando la función RESIDUO, que en Excel 2003 produce el error #¡NUM! si el dividendo de la división que ha de procesar es ≥ 134.217.728 (2²⁷) veces el divisor, y a partir de Excel 2007 si el dividendo es ≥ 1.125.900.000.000 veces el divisor (comentario sobre este error en las FAQs).

Por lo tanto, es necesario calcular los restos de las divisiones prescindiendo de la función RESIDUO, lo que complica un poco la fórmula (aunque no aumenta su cantidad de anidamientos, que es lo importante):

{=SI(ESNUMERO(COINCIDIR(A1;{2;3;5;7};0));VERDADERO;SI(SUMA(--(A1-ENTERO(A1/{2;3;5;7})*{2;3;5;7}=0))>0;FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/10;0)))-1)*10)=A1))=1))}

En este grupo de fórmulas cabe destacar que se están utilizando literales de matriz dispuestos tanto en columnas ({1\3\7\9}) como en filas ({2;3;5;7}), por lo que si los separadores en el equipo fuesen otros habría que hacer las modificaciones necesarias.

El número más alto que pruede procesar esta fórmula se puede calcular usando:

El aumento de capacidad de la fórmula anterior con respecto a la que la precedía se basó en dos factores: de una parte, al evitar tener que procesar los números terminados en 5 se obtuvo una mejora del 20% y, de otra, como la nueva fórmula trabaja con una matriz de cuatro columnas en lugar de una columna, se cuadruplica su capacidad.

Llegados a este punto, no es posible seguir optimizando la fórmula mediante la eliminación de las terminaciones que no son necesarias, puesto que los números terminados en las que quedan (1, 3, 7 y 9) sí pueden ser primos. La posible mejora tan sólo podría provenir entonces desde la otra parte de la fórmula, es decir, la matriz en la que se almacenan los números que le sirven a MULTIPLO.INFERIOR como segundo argumento.

Analicemos pues el literal de matriz usado por la fórmula precedente: {1\3\7\9} puede ser considerado una especie de base a partir de la cual la fórmula construye la matriz bidimensional, sumándole 10 a cada uno de sus elementos cada nueva fila.

Pero ¿por qué limitarnos a 4 columnas? Excel dispone de más columnas: 256 en la versión 2003 ó 16.384 en las versiones 2007 y 2010, de forma que nada nos impide que el literal de matriz base tenga más de cuatro columnas.

{1\3\7\9\11\13\17\19\21\23\27\29\31\33\37\39\41\43\47\49\51\53\57\59\61\63\67\69\71\73\77\79\81\83\87\89\91\93\97\99}

Al hacer esto, estamos multiplicando por 10 el número de columnas que tendrá la matriz (ahora serán 40 columnas), y este aumento de capacidad nos permitirá, por fin, llegar al límite de la precisión numérica de Excel (999.999.999.999.999). De hecho, la fórmula podría procesar números más grandes de no ser por este límite en la precisión de Excel.

La nueva fórmula es, conceptualmente hablando, idéntica a la anterior si bien, como es lógico, resulta más larga, puesto que el literal de matriz también lo es:

{=SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9\11\13\17\19\21\23\27\29\31\33\37\39\41\43\47\49\51\53\57\59\61\63\67\69\71\73\77\79\81\83\87\89\91\93\97\99}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/100;0)))-1)*100)=A1))=1}

Tiene los mismos problemas y limitaciones que la fórmula número 3... multiplicados por 10. Pero las soluciones a estos problemas son las mismas que las que usamos en esa fórmula. Por lo tanto, la fórmula definitiva que nos permite llegar al límite de la precisión numérica de Excel es:

{=SI(ESNUMERO(COINCIDIR(A1;{2;3;5;7;11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97};0));VERDADERO;SI(SUMA(--(A1-ENTERO(A1/{2;3;5;7;11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97})*{2;3;5;7;11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97}=0))>0;FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;{1\3\7\9\11\13\17\19\21\23\27\29\31\33\37\39\41\43\47\49\51\53\57\59\61\63\67\69\71\73\77\79\81\83\87\89\91\93\97\99}+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/100;0)))-1)*100)=A1))=1))}

La fórmula es ciertamente muy larga, pero esto se debe sobre todo a la presencia de los cuatro literales de matriz. Si analizásemos su sintaxis y la comparásemos con la de la 3ª fórmula, veríamos que ambas son idénticas y que, de hecho, la fórmula no es demasiado complicada, afirmación que puede parecer un sarcasmo puesto que tiene nada menos que 352 caracteres; pero si creásemos un rango con nombre llamado, por ejemplo, Primos_1ª_Centena que se refiriese al literal de matriz {2;3;5;7;11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97} y otro rango con nombre llamado, por ejemplo, _1_3_7_9_1ª_Centena que se refiriese al literal de matriz {1\3\7\9\11\13\17\19\21\23\27\29\31\33\37\39\41\43\47\49\51\53\57\59\61\63\67\69\71\73\77\79\81\83\87\89\91\93\97\99}, la fórmula podría ser reescrita así:

{=SI(ESNUMERO(COINCIDIR(A1;Primos_1ª_Centena;0));VERDADERO;SI(SUMA(--(A1-ENTERO(A1/Primos_1ª_Centena)*Primos_1ª_Centena=0))>0;FALSO;SUMA(--(MULTIPLO.INFERIOR(A1;_1_3_7_9_1ª_Centena+(FILA(INDIRECTO("1:"&REDONDEAR.MAS(RAIZ(A1)/100;0)))-1)*100)=A1))=1))}

y, como se puede ver, no resulta demasiado complicada desde el punto de vista sintáctico.

Respecto al rendimiento de esta fórmula, lo cierto es que me ha parecido sorprendemente bueno para la ingente cantidad de cálculos que ha de hacer si el número a procesar es muy grande. La he probado en dos computadoras, ambas con la versión 2010 de 32 bits de Excel: en una con procesador Intel Core 2 Duo a 2,93 GHz y Windows 7 - 32 bits la fórmula tarda unos 6 segundos en determinar que el 999.999.999.999.989 es primo (de hecho, es el primo más alto que puede encontrar la fórmula). En otra computadora, mi portátil equipado con procesador Intel Core i7-720QM 1,6GHz-2,8GHz y Windows 7 - 64 bits este mismo resultado se obtiene en algo más de 3 segundos.

Hablar de segundos cuando estamos acostumbrados a que Excel nos devuelva el resultado de una fórmula nada más pulsar la tecla Entrada quizás pueda parecer mucho, pero seguramente no lo parecería tanto si se conociese el enorme tamaño de la matriz que ha de crear en este caso y se considerasen los cálculos que debe hacer con cada uno de sus elementos. El tamaño de la matriz es sencillo de calcular. Por ejemplo, para el número 999.999.999.999.989 la fórmula es:

que nos dirá el número de elementos de la matriz: 12.649.120; y hay que tener en cuenta que sobre esos más de 12 millones de elementos la fórmula ha de hacer varias operaciones.

El número más alto que puede procesar esta última fórmula está determinado por esta otra:

que en Excel 2003 devuelve el número 42.949.672.960.000. Dado que este número es inferior al límite máximo de la fórmula número 3, no tiene ningún sentido utilizar ni en esta versión ni en las anteriores la 4ª, puesto que es bastante más larga.

en Excel 2010, la fórmula nos devolverá el número máximo al que podría llegar en esta versión la fórmula nº. 4 de no ser por el límite de 15 dígitos en la precisión numérica: el 10.995.116.277.760.000, es decir, casi 11 veces superior a dicha precisión numérica máxima.

AVERIGUAR SI UN NÚMERO ES PRIMO USANDO UNA FÓRMULA