Esta regexp en Perl comprueba si un número es primo o no / Avinash Meetoo

En los últimos meses descubrí un par de curiosidades sobre fórmulas para generar números primos y comprobarlos, entendiendo por «fórmulas» o bien una función matemática o bien un programa sencillo que genera todos los números primos o que comprueba su primalidad.

Ya hace siglos que Euler vio que n² - n + 41 genera toda una serie de números primos… pero sólo entre el 1 y el 40… ¿Sería una serie válida para generar más números primos? Pues no: con n = 41 la fórmula da como resultado 1681 que resulta ser el producto de 41 × 41, algo obvio al examinar la fórmula.

La idea de multiplicar todos los números primos en secuencia y sumarles 1 tampoco sirve. Veamos un ejemplo:

2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031

pero resulta que 30031 = 59 × 509. La idea deja de ser válida porque la multiplicación crece muy rápido y puede tener factores primos por encima de los que se están multiplicando, algo que no se ha tenido en cuenta en la idea original.

La fórmula para generar primos de C.P. Willans

¿Es posible que exista una fórmula para generar todos los números primos por su orden? Siempre había oído que teóricamente no existen, y que encontrar «el siguiente número primo» es laborioso. Pero resulta que sí que existen… aunque su utilidad como se explica más adelante …