12 de noviembre de 2013

10001st prime - Project Euler, problema 7

El problema es el siguiente:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
Sería tentador, que como dice en la descripción, "listaramos" (guardar en una lista) los n primos, pero es claro que no es necesario, tan solo queremos el 10001-ésimo primo, afortunadamente en Matlab y en Octave contamos con una herramienta preprogramada llamada isprime, por lo que el código es realmente muy sencillo, pero les advierto que es algo lento, al menos en octave:


c=1;
i=3;
p=2;
while c<10001
 if isprime(i)
  p=i;
  c+=1;
 end 
 i+=2;
end
p

La explicación es sencilla:
c cuenta cuantos primos van, e inicia en 1 porque ya "se contó" el 2.
i recorre los impares empezando desde el 3 (por eso c=1 inicialmente), en búsca de primos :P
p es donde se almacena el número i actual si es primo.

El while sigue avanzando hasta que se cuenten 10001 primos, en cada iteración verifica si i es primo, y de serlo, lo "guarda" en p, y aumenta el contador c,  en cualquier caso i se incrementa en 2 (ningún par, con excepción del 2, es primo).
Finalmente se imprime p, que es la solución al problema.

Debo confesar que sospeché que sería lento, así que abrí la consola de ruby para evitar un ataque de impaciencia, e hice lo siguiente:

require "prime"
puts Prime.first 10001

que funcionó en una fracción de segundo a diferencia de mi código en octave.


EDIT: No entiendo por qué a veces el último artículo que publico sale como si lo hubiera publicado antes (Estoy haciendo los problemas en orden). ¿Alguien tiene alguna idea?