Lo que he aprendido: generar números primos en Haskell

Os conté hace tiempo que me había dado por aprender Haskell para entretenerme. Hoy os voy a contar un efecto colateral: he descubierto una nueva manera de hallar números primos.


Hasta ahora para filtrar los números primos de entre los naturales, hacía lo que se conoce como división por tentativa, es decir, ir probando si cada número era divisible por los números primos menores que él.

Implementado en Haskell quedaría algo así:

Así, si queremos saber cuáles son los números primos por debajo de 25, haríamos:

> primos 25
> [2,3,5,7,11,13,17,19,23]

Como podéis ver, esto no es muy eficiente que se diga. Aquí es donde nos viene al rescate la Antigua Grecia y lo que se conoce como la Criba de Eratóstenes. Consiste en lo siguiente:

  1. Escribimos una lista de los números naturales empezando en 2
  2. Marcamos el primer valor de la lista p como número primo
  3. Eliminamos los múltiplos de p de la lista
  4. Volvemos al paso 2

En la imagen se puede ver el algoritmo en acción, es un trucazo de lo más inteligente:

Bien, vamos a implementarlo en Haskell:

Ahora si llamamos a la función primos nos dará una lista infinita de números primos. Pero, ¿y si queremos solo unos pocos? Pues utilizamos una de las características más elegantes de Haskell: la evaluación perezosa. Unos ejemplos serían:

De esta manera podríamos aplicar las condiciones que queramos a nuestra lista gigante de primos y solo se evaluará lo que sea necesario.


Nada más por hoy. ¡Ánimo con las comidas navideñas y empezad bien el año todos! 😀

Fuentes

Código de la división trivial: Programming in Haskell de Graham Hutton

Fuente de la imagen de la criba

Código de la implementación de la criba

Más

Why functional programming matters?

Anuncios

¡Opina sin miedo! (Puedes usar Markdown)

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s