Sencillo algoritmo de cálculo de números primos

Se dice que el método más efectivo, pero mas lento, es el llamado “la cuenta de la vieja“. Básicamente, consiste en no usar atajos, sino usar la definición. Por ejemplo, 23 es 2*2*2, que viene siendo 2+2+2+2.

Para números grandes es muy costoso, porque como es obvio, tardaríamos mucho. Pero gracias a los ordenadores, que son capaces de hacer cantidades ingentes de operaciones, el trabajo es muy rápido.

Para la calculación de números primos, el método de la vieja sería el de la definición de número primo:

El conjunto de los números primos es un subconjunto de los números naturales que engloba a todos los elementos de este conjunto mayores que 1 que son divisibles únicamente por sí mismos y por la unidad.

Wikipedia.org

Es fácil: Dividimos un número entre todos los primos conocidos que sean menores que él (sin contar al uno como primo). Si el resultado de todas las operaciones deja resto (si operamos con números enteros, si operamos con reales sería si la operación deja decimales), entonces ese número es primo.

Como dividirlo entre todos los números primos es una exageración, estableceremos un límite en sqrt(n) (raiz cuadrada de n), siendo n el número que queremos comprobar.

Se escoge sqrt(n) debido a que todos los números que dividen a n se encuentran en dos mitades, los menores que sqrt(n) y los mayores. Los que son mayores que sqrt(n) son el resultado de dividir n entre un número menor que sqrt(n). La demostración matemática de esto, sencillamente, no la recuerdo :P.

Otra forma de optimizar el proceso es limitar la comprobación a los números impares, y obviando la comprobación de que sea divisible entre 2. Así nos ahorramos dividir un número par entre 2, que ya sabemos que nos va a dar un número no primo y dividir un número impar entre 2, ya que sabemos que 2 no divide números impares.

Puede parecer una chorrada, pero cualquier ahorro es un gran ahorro, porque se repetirá durante mucho tiempo.

El algoritmo, en pseudocódigo, sería entonces:

Variables:

  • lista : Lista de todos los números primos.
  • n: número que queremos comprobar si es primo o no.
  • primo: Número primo que comprobaremos si divide a n.
  • limite: sqrt(n), sólo se comprueban los números primos menores o iguales a este número.
  • es_primo: Variable booleana de control. Indica si un número es primo o no. Se inicializa a VERDADERO.

Programa:

1. Inicializamos n {Nota: Si sólo queremos comprobar ese número, no puede ser mayor que el mayor primo almacenado al cuadrado, si queremos hacer una lista de primos no puede ser mayor que el último primo almacenado}
2. Mientras n < máximo {el número más grande con el que puede operar el lenguaje} hacer

1. {Inicialización de variables:} es_primo=VERDADERO limite=sqrt(n) primo=primer_primo(lista)
2. Mientras (es_primo=VERDADERO) y (primo<=limite) y (lista no ha acabado) hacer

1. Si (entero módulo primo) = 0
2. entonces es_primo=FALSO
3. Sino: primo=siguiente_primo(primo, lista)

3. Fin Mientras
4. Si es_primo=verdadero
5. entonces almacenar_primo(primo, lista)
6. n=n+2 {recordemos que solo comprobamos los números impares}

3. Fin Mientras

Lo probé en Pascal, siendo la lista un archivo de texto (para poder publicarla después en este mismo blog) y comprueba un millón de números en pocos minutos, aunque como es obvio cada vez tardará mas. Ahora mismo, después de 3 horas aproximadamente, ha superado ya el número 37*106. Esa misma lista ocupa unos 20 Mb, así que probablemente la suba a Megaupload o a un sitio de esos.

About these ads

1 Comentario

  1. Ese mismo algoritmo (no exactamente), lo implementé yo hace unos días en python.
    Si quieres verlo, lo publiqué en mi blog.

    Sé que existen otros métodos más eficientes como el test de Miller Rabin, pero este es más sencillo y es más eficiente para números “pequeños”.

    Si quieres ver mi implementación:

    http://entrecerosyunos.wordpress.com/2009/06/15/buscando-numeros-primos/


Comments RSS TrackBack Identifier URI

Deja un comentario

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

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.