Project Euler: Problem 10

http://projecteuler.net/index.php?section=problems&id=10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Another "prime number" question. Let's reuse and adapt our solution from problem 7:

def f1(n):
    # Define test for primeness
    def isprime(x):
        if x <= 1: return False

        c = 2

        while c <= x**0.5:
            if x%c == 0:
                return False

            if c != 2:
                c += 2
            else:
                c += 1

        return True

    # Iterate over odd numbers and test for primeness
    res = 2

    for i in xrange(3,int(n),2):
        if isprime(i):
            res += i

    # Return the sum
    return res

This is starting to feel slow, though. On my machine, the correct result is returned in about 47 seconds. I'm gonna have to either better optimize my prime generation algorithm or find a new one altogether.

Project Euler: Problem 9

http://projecteuler.net/index.php?section=problems&id=9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a^(2) + b^(2) = c^(2) For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2). There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

To generate the triplets, we'll use Euclid's formula (http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple).

def f1(x):
    m,n = 1,0

    while True:
        m += 1

        # No solution?
        if (2*m*m + 2*m) > x:
            return None

        for n in xrange(1,m):
            # Euclid's formula
            a = m*m - n*n
            b = 2*m*n
            c = m*m + n*n

            if (a+b+c) == x:
                return a*b*c

Obviously there are many possible input values for which there are no solutions. In these cases, since 1 is the lowest possible value for n, we can check to see if m has become too large. That's the point of the "return None" statement above.