Fermat vs. Pythagoras mejorado

Logré bajar la complejidad de mi solución de un orden cúbico a un orden cuadrático, la diferencia en cuanto a tiempo de ejecución requerido es sorprendente:

Pero todavía no e suficiente, con un N igual a 10000 la respuesta se obtiene luego de 10 minutos (en mi computadora de 700 Mhz).

En esta solución ya no uso la función pythagoras(x,y,z). Solo hay 2 ciclos for anidados y el valor de z se calcula como z = sqrt( pow(x,2) + pow(y,2) ). Si z es entero, se tiene un triplete válido y solo falta verificar si x,y,z son primos relativos.

def is_int(i):
return i == int(i)



def solv106f(N):
miembros = []

tripletes_rprim = 0

for x in range(1,N-1):

    for y in range(x+1,N):

        z = sqrt( pow(x,2) + pow(y,2) )

        if (is_int(z) and z <= N):

            for a in [x,y,z]:

                if a not in miembros:

                    miembros.append(a)

            if (rprim(x,y,z)):

                tripletes_rprim +=1



no_miembros = N - len(miembros)

return N, tripletes_rprim, no_miembros