#### 11 Jun 2011 maragato»(Master)

Euler 9

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #9 statement is –

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 .

Find the product .

Butt ugly, super slow, brute-force solution:

 ```1 2 3 4 5 6 7 8 9 10 11 12 ``` ```from sys import exit   def is_triplet(a, b, c):         if a < b and b < c:                 return a ** 2 + b ** 2 == c ** 2   for a in range(0, 1000):         for b in range(a + 1, 1000):                 for c in range(b + 1, 1000):                         if a + b + c == 1000 and is_triplet(a, b, c):                                 print a * b * c                                 exit(0)```

I’ll have to rethink this, as it’s really inefficient. As it is, it runs in 18.034s!

Updated 2010/08/04: Gustavo Niemeyer pointed an obvious optimization to the algorithm above (written in C)–the innermost loop is unnecessary. I rewrote it in Python to see the difference:

 ```1 2 3 4 5 6 7 8 9 10 ``` ```from sys import exit   def is_triplet(a, b, c):         return (a ** 2 + b ** 2 == c ** 2)   for a in range(1, 1000):         for b in range(a + 1, (1000 - a) / 2):                 c = 1000 - a - b                 if is_triplet(a, b, c):                         print "%d * %d * %d = %d" % (a, b, c, a * b * c)```

From 18s to 0.076s. As well, following Eduardo Habkost’s suggestion, I used psyco and execution time went down to 0.023s.

Syndicated 2010-08-03 17:45:17 from Roberto Teixeira's blog

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.