Why is this loop heavy code so slow in Python? Possible Project Euler spoilers

[Arnaud Delobelle]

On Sep 2, 12:51 pm, jwrweather... at gmail.com wrote:
> I'm pretty new to python, but am very happy with it. As well as using
> it at work I've been using it to solve various puzzles on the Project
> Euler site -http://projecteuler.net. So far it has not let me down,
> but it has proved surprisingly slow on one puzzle.
>
> The puzzle is: p is the perimeter of a right angle triangle with
> integral length sides, {a,b,c}. which value of p  < 1000, is the
> number of solutions {a,b,c} maximised?
>
> Here's my python code:
>
> #!/usr/local/bin/python
>
> solutions = [0] * 1001
> p = 0
>
> for a in xrange(1, 1000):
>     for b in xrange(1, 1000 - a):
>         for c in xrange(1, 1000 - a - b):
>             p = a + b + c
>             if p < 1000:
>                 if a ** 2 + b ** 2 == c ** 2:
>                     solutions[p] += 1
>
> max = 0
> maxIndex = 0
> index = 0
> for solution in solutions:
>     if solution > max:
>         max = solution
>         maxIndex = index
>     index += 1
>
> print maxIndex
>
> It takes 2 minutes and twelve seconds on a 2.4GHz Core2Duo MacBook
> Pro. Surprised at how slow it was I implemented the same algorithm in
> C:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main() {
>   int* solutions = calloc(1000, sizeof(int));
>
>   int p;
>   for(int a = 1; a < 1000; ++a) {
>     for(int b = 1; b < 1000 - a; ++b) {
>       for(int c = 1; c < 1000 - a - b; ++c) {
>         p = a + b + c;
>         if(p < 1000) {
>           if(a * a + b * b == c * c) {
>             solutions[p] += 1;
>           }
>         }
>       }
>     }
>   }
>
>   int max = 0;
>   int maxIndex = 0;
>
>   for(int i = 0; i < 1000; ++i) {
>     if(solutions[i] > max) {
>       max = solutions[i];
>       maxIndex = i;
>     }
>   }
>   printf("%d\n", maxIndex);
>   return 0;
>
> }
>
> gcc -o 39 -std=c99 -O3 39.c
>
> The resulting executable takes 0.24 seconds to run. I'm not expecting
> a scripting language to run faster than native code, but I was
> surprised at how much slower it was in this case. Any ideas as to what
> is causing python so much trouble in the above code?

from math import sqrt

solutions = [0] * 1001
p = 0

for a in xrange(1, 1000):
    a2 = a*a
    for b in xrange(1, 1000 - a):
        c = sqrt(a2 + b*b)
        if c == int(c) and a+b+c < 1000:
            solutions[a+b+int(c)] += 1

max = 0
maxIndex = 0
index = 0
for solution in solutions:
    if solution > max:
        max = solution
        maxIndex = index
    index += 1

print maxIndex

--
Arnaud