Proyectos que avanzan

Por un lado, Cursed Night ya ha avanzado un poco. Bastante poco, pero ha avanzado.

Y por otro lado, la lista de números primos cuenta ya con más de 10 millones de números. Dentro de poco serán publicados en 100 cómodas listas de 1 Mb cada una. NOTA: NO se garantiza que sean números primos. En principio debería serlo, puesto que no se ha detectado ninguna anomalía en la lista demasiado grande; pero basta con que falte uno para que gran parte del trabajo se haya ido al garete.

Permanezcan a la espera ^^.

Anuncios

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.

Ahora que llega el calor, es hora de quedarse en casa

Fuck yes.

Y es que es lo divertido del sistema educativo: las mejores vacaciones son también las justamente anteriores a los examenes de recuperación.

No es un relación causal.

No son las mejores por ser las justamente anteriores a los examenes de recuperación.

Son las mejores por ser las de verano.

Los examenes de recuperación son lo que las estropean…

Jooo

Pero bueno, 9 meses de vacaciones que fue el curso que se ha acabado bien valen un par de ellos de trabajo…

Lástima que sean los mejores…

Aunque claro, eso no tiene nada que ver con el título.

Es que ahorita tengo pisina ^^.

Post escrito integramente en párrafos monofrasaicos