9 de julio de 2012

Project Euler 10

Hace bastante tiempo solía programar de manera habitual, ahora quice retomar algo de eso, y estoy rehaciendo los problemas de projecteuler.net desde cero, usando python para ello.  Cabe señalar que no soy el "gran programador", pero me gusta programar, así que trataré de publicar y explicar mis soluciones aquí.

Long ago i used to program, now i wanted to do it again and i'm redoing projecteuler.net  problems from the beginning using python. I'm not a great programmer, but i like it, so i'll try to publish and explain my solutions here.


Aquí tienen mi solución al 10:

Here is my solution to 10th problem:
#!/usr/bin/env python
from math import sqrt

def isprime(n):
    if n==1:
        return 0
    if n==2:
        return 2
    if n%2==0:
        return 0
    m = int(sqrt(n))
    for i in range(3,m+1,2):
        if n%i==0:
            return 0
    return n

print sum(map(isprime,range(int(2e6))))
Mi solución es bastante lenta, pero compacta.
isprime, regresa 0 si el número no es primo, y el número si éste es primo, aproveché esta función y la usé junto con map, para generar una lista, en un rango de 2 millones (el int(2e6) es innecesario, solo fue la flojera que me ganó). A eso último le apliqué sum, para sumar toda la lista.

My solution is very slow, but compact.
isprime returns zero if the number is not prime, and the number if it's prime. I took advantage of that function using it with map to generate a list of 2 million elements (so int(2e6) is just me not wanting to write a few characters :P). Then i used sum, well... to sum up the elements of the list.


Estoy seguro que una criba con un yield o algo parecido hubiese sido muchísimo mas rápido, pero ya había hecho una función isprime muy parecida, así que solo la modifiqué, y agregué la última linea, eso es mucho mas rápido de programar.

I'm pretty sure that a sive (using a sieve and that stuff) would've been much faster, but using a similar isprime i already had was so much faster to write.

Update:
Cuando pulsé publicar, me percaté de que pude haber una solución menos fea sin moficar la función isprime que ya tenía:

Just when i clicked "publish" i thought that i could've programmed a less ugly solution without even modifiing my original isprime fuction:


#!/usr/bin/env python
from math import sqrt

def isprime(n):
    if n==2:
        return True
    if n%2==0:
        return False
    m = int(sqrt(n))
    for i in range(3,m+1,2):
        if n%i==0:
            return False
    return True

print sum(filter(isprime,range(int(2e6))))
 No hay diferencia significativa en la velocidad, pero es una solución menos fea.

Not a noticeable difference in speed, but it's a less ugly solution.