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

[jwrweatherley at gmail.com]

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?