Criba de Eratostenes

Hola, antes habia puesto un par de algoritmos para saber si un numero era primo, pero y si queremos saber la cantidad de primos en un intervalo dado? Tardariamos mucho si el intervalo es muy grande. Asi que lo mejor para este caso es usar el algoritmo de la criba de eratostenes.

Lo que se hace, es tomar un primo y tachar todos los multiplos de ese primo, luego tomamos el siguiente numero no tachado(que seria un primo) y eliminamos todos sus multiplos, y asi sucesivamente, hasta que todos los no primos se hayan tachado en el intervalo. Pero como sabemos eso? Pues bien, esto lo sabemos porque como se dijo antes solo necesitamos iterar hasta la raiz de un numero para saber si es primo. Es decir que cuando lleguemos a la raiz del maximo numero del intervalo habremos eliminado todos los no primos.

Asi pues, el algoritmo en java para hacer esto seria:

public static boolean criba(int n){
 boolean primos[] = new boolean[n+1];
 Arrays.fill(primos,true);
 primos[0] = primos[1] = false;
 for(int i=2;i<(int)Math.sqrt(n)+1;i++)
  if(primos[i])
   for(int j=i*i;j<primos.length;j+=i)
    primos[j] = false;
 return primos;
}

Con el primer ciclo recorremos los numeros hasta la raiz cuadrada, y con el segundo tachamos sus multiplos si el numero "i" es primo. De esta forma los valores que queden en true seran los primos, es decir primos[2] sera true.

El algoritmo en C podria ser algo como lo siguiente:

char* criba(int n){
 char *p = (char*)malloc((n+1)*sizeof(char));
 memset(p,' ', n+1);
 n = n+1;
 int i=0,j=0;
 int f = sqrt((double)n)+1;
 p[0] = p[1] = 'n';
 for(i=0;i<f;i++)
  if(p[i]==' ')
   for(j=i*i;j<n;j+=i)
    p[j]='n';
 return p;
}

Y en C los valores que queden con una 'n', no seran primos y los que queden con ' ' seran los primos, eso ya es de gustos :)

Si hay alguna pregunta o algo que agregar, comenten.

PD: les dejo unos cuantos problemas en los cuales hay que aplicar la criba para resolverlos.
http://www.codechef.com/problems/PRPALIN
http://projecteuler.net/problem=7
http://projecteuler.net/problem=10
http://projecteuler.net/problem=249

Exponenciacion binaria y modular

Hola, estuve haciendo un par de cosas y tuve que usar un algoritmo de exponenciacion binaria y modular pero no queria que fuera recursivo asi que luego de algunos intentos, esto fue lo que consegui, espero les pueda servir de ayuda, tanto como a mi(aunque esta en java se entiende si manejas otro lenguaje :P) :

public static int expomod(int a, long b,int mod){
    int res = 1;
    while(b>0){
        if((b&1)==1)
            res=(a*res)%mod;
    b>>=1;
    a=((a%mod)*(a%mod))%mod;
    }
return res;
}

y el algoritmo en python es:

def ex(a, b,m):
     r = 1
     while(b):
             if(b&1):
                     r = (r*a)%m
             b>>=1
             a = ((a%m)*(a%m))%m
     return r

La verdad luego de ver el algoritmo recursivo, se entiende este. Lo que se hace es cambiar la recursividad a las variables, por decirlo de alguna forma. Saludos y espero sus comentarios!

Un buen tutorial donde se tratan a fondo otros algoritmos relacionados es este de topcoder.

Nota: un problema en donde se puede aplicar este algoritmo es este.

Generar particiones de un numero

Hola, a veces necesitamos generar las particiones de un numero, una partición es una forma de escribir un numero entero positivo como la suma de otros numeros enteros positivos. Por ejemplo:

Para 3, las particiones serian:
1+1+1, 2+1, 3

Ahora, podemos necesitar los numeros que conforman las particiones o simplemente cuantas particiones tiene. Para este caso, explicare como obtener el numero de particiones con programacion dinamica y modificando este algoritmo se puede obtener que numeros conforman cada una de las particiones.

La pregunta es como llegamos a que las particiones de 3, en este caso, son esas. Bien, luego de ver varios ejemplos(el 4 y el 5) si ordenamos las particiones nos daremos cuenta de algo:

Particiones hasta 5:
N. 1:
1

N. 2:
11
2

N. 3:
1 11
1 2
3

N. 4:
1 111
2 11
2 2
3 1
4

N. 5:
1 1111
2 111
2 21
3 11
3 2
4 1
5

Si nos damos cuenta, las particiones del 3 tienen a las del 2. Las del 4 tienen las del 3 y las del 2 y asi sucesivamente.

En otras palabras, podemos formar un numero de la siguiente forma(para el 4 por ejemplo):

1 + alguna forma de escribir el tres (4-1)
2 + alguna forma de escribir el dos (4-2)
3 + alguna forma de escribir el uno (4-3)
4 (solo hay una forma de escribir el numero con el mismo)

Entonces si quisieramos hacerlo para un numero y obtener todas las particiones hariamos algo como:

1+p(numero-1)
2+p(numero-2)
...
(n-1)+p(numero-(n-1)) es decir p(3) para el caso de las particiones de 4
n
p(numero) serian las particiones o el numero de particiones del numero
Y estas serian todas las particiones de n

El algoritmo para hacer esto en python seria:

numero = 5
particiones = [1] + [0] *numero
for i in xrange(1,numero+1):
    for j in xrange(i, numero+1):
        particiones[j] +=particiones[j-i]
    #print(particiones)
print(particiones[numero])

La ejecucion de este programa daria lo siguiente:
[1, 1, 1, 1, 1, 1]
[1, 1, 2, 2, 3, 3]
[1, 1, 2, 3, 4, 5]
[1, 1, 2, 3, 5, 6]
[1, 1, 2, 3, 5, 7]

y en cada iteracion sucede, tomamos un valor y anadimos las particiones del valor que falta para completar el numero.

particiones[j] = particiones que lleve + formas de hacer el valor que falta (j-i)

Podriamos modificar este algoritmo y en vez de solo sumar, agregar cada una de las particiones y asi obtendriamos los valores que conforman estas particiones

Tambien hay una formula recursiva dada por Euler para obtener las particiones de un numero.

Nota: este problema esta relacionado con un problema muy conocido que consiste en saber de cuantas formas diferentes se puede devolver una cantidad de dinero usando solo las denominaciones dadas.

Nota2: una pregunta interesante es como hacer para que en las particiones un valor no aparezca mas de una vez, sin necesidad de validar luego de haber obtenido las particiones.

Espero les sirva!

Project euler problema 1 (A papel y lapiz)

Estaba revisando un libro sobre sumatorias y recordé este problema de PE( projecteuler.net/problem=1 ): hay que sumar los números menores a 1000 que son múltiplos de 3 o de 5.

El problema es muy simple si sabes algún lenguaje de programación y lo básico(estructuras de repeticion y de selección) entonces será sencillo. Una forma posible diferente a la común es (en python):

sum(range(3,1000,3)) + sum(range(5,1000,5)) - sum(range(15,1000,15))

Lo que hace es sumar todos los múltiplos de 3, luego los de 5 y restarle los de 15, ya que cuando hizo los de 3 (3,6,9,12,15...)y los de 5(5,10,15...) contó dos veces los múltiplos de 15.

Bueno pero esta forma es muy común y muy simple, así que la abordé desde el punto de vista de las sumatorias, primero algo básico:

La sumatoria de los n primeros enteros positivos(1+2+...n) es: n*(n+1)/2

En este problema queremos sumar los múltiplos de 3 menores a 1000. Los múltiplos de 3 los podemos expresar mediante: 3*i. De la misma forma expresaremos los múltiplos de 5( 5*i)

Ahora si son los múltiplos menores a 1000, pues será la suma desde 1, hasta [999/3] de 3*i (donde [ ] es la parte entera) y lo mismo con los múltiplos de 5. Luego le restaremos los múltiplos de 15 y tendremos la respuesta. Con la fórmula anterior tendríamos que(la constante se puede escribir por fuera de la sumatoria):

3*(n*(n+1)/2) = 3*(333*334/2)
Igual para 5 y 15, y luego los sumamos(restamos la de 15 por lo que se dijo antes):

Solución = (3×333×334÷2)+ (5×199×200÷2) − (15×66×67÷2)

De esta forma obtenemos la solución para el primer problema de PE de una forma bastante rápida(Si es que no es la más rápida y sencilla una vez que sabemos cómo abordarlo con sumatorias). Si tienes alguna solución diferente, coméntala!

Test de primalidad

Cómo saber si un número es primo? Muchas veces necesitamos crear un algoritmo para saber si un número es primo o no. Pues bien, no se trata de una tarea muy difícil, si están participando en alguna competencia, seguro les servirá alguno de los siguientes algoritmos.

Un número es primo si sólo es divisible por él mismo y la unidad. Por definición el uno no es primo.

2,3,5,7,11,13,17,19,23,29...

Si queremos escribir el código para saber si un número es primo tendríamos que iterar desde 1 hasta el número y preguntar y esos números dividen a n. Si al final sólo 2 lo dividen, entonces el número es primo. (Un número i divide a n si el residuo de la división es 0, es decir si la división es exacta, si el % es 0)

cont = 0;
for(int i=1;i<=n;i++)
    if (n%i==0)
        cont+=1;
if(cont==2)
    System.out.println("Primo");
else
    System.out.println("No es primo");

o podriamos iterar desde 2 hasta uno antes que n y si algun numero divide a n, estos serian diferentes a 1 y a n, entonces no es primo:

boolean primo = true;
for(int i=2;i<n;i++)
    if (n%i==0){
        primo = false;
        break;
    }
if(primo)
    System.out.println("Primo");
else
    System.out.println("No es primo");

Estas son las formas que se nos ocurren a todos, y es fácil de pensar pero no es muy eficiente, ya que si pusiéramos un número un poco más grande...o mejor aún varios números tardaría bastante. Una pequeña mejor que le podemos hacer es sólo iterar hasta la mitad del número(incluyéndolo) ya que un número no tiene divisores más allá de su mitad. Pero algo aún mejor es sólo iterar hasta la raiz cuadrada del número ya que si dividimos un número por un número más grande que su raíz cuadrada el cociente será un número menor a su raíz. Por ejemplo:

16/8=4

Lo que es igual a la raíz cuadrada.

Mucho más simple si tan pronto encontramos un divisor decimos que n no es primo:(además si descartamos si es par, ya sabemos que no es primo o si es uno y luego sólo iteramos a través de los impares):

if((n&1)==0 && n!=2) || n==1) return false;//si es par y es diferente de 2 porque el 2 es primo
for(int i=3;i<=Math.sqrt(n);i+=2)
    if(n%i==0)
        return false;
return true;

Existen otras formas más complicadas pero más eficientes de saber si un número es primo, para complementar me gustaría compartir una regex que encontré por ahí para verificar si un número es primo en binario:

http://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex

Algo de awk

Necesitaba enviar algunos parámetros a un script en awk, el problema es que eran varios, mi solución fue:

$ awk -v param1=$var1 -v param2=$var2 '{acciones}'

De esta forma se tenía los parámetros necesitaba usar.

Algunos tutos y libros interesantes para aprender awk:
    - http://www.linux-es.org/node/31
    - http://www.lawebdelprogramador.com/cursos/AWK/5752-Guia_del_usuario_para_AWK.html

Renombrar archivos masivamente desde consola

En ocasiones nos encontramos con que tenemos muchos archivos que tienen una extensión que nos gustaría cambiar o que tienen alguna cadena que nos gustaría quitar. Por ejemplo tener muchos archivos que digan: nombreDelArchivo-NombreAutor, o cosas por el estilo. Esto es algo muy sencillo de arreglar con la orden rename.

Una de las formas de aplicarlo es:

rename 's/cadenaAreemplazar/cadenaNueva/' archivosAaplicar

Por ejemplo, supongamos que tenemos muchos archivos, para este caso que los archivos fueron generados por el siguiente script:


#!/bin/bash
   echo "Comenzando la ejecucion"
   for i in $(seq 2 10)
   do
   touch archivo$i\(Nombre\)
   done
   echo "Finalizado correctamente"

Cuando haya finalizado la ejecución tendremos varios archivos: archivo1(Nombre), archivo2(Nombre), etc

Si quisiéramos quitar la cadena "(Nombre)" de cada uno de ellos, sería ejecutar:

$ rename 's/\(Nombre\)//' *\(Nombre\)

La parte final del comando toma todos los archivos cuyo nombre contenga la cadena "(Nombre)" en la carpeta que estamos trabajando.