def pythag_triples(n): i = 0 start = time.time() for x in range(1, int(sqrt(n) + sqrt(n)) + 1, 2): for m in range(x+2,int(sqrt(n) + sqrt(n)) + 1, 2): if gcd(x, m) == 1: # q = x*m # l = (m**2 - x**2)/2 c = (m**2 + x**2)/2 # trips.append((q,l,c)) if c < n: i += 1 end = time.time() return i, end-start print(pythag_triples(3141592653589793))Estoy tratando de calcular triples pitagóricos primitivos usando la idea de que todos los triples se generan a partir del uso de m, n que son impares y coprimos. Ya sé que la función funciona hasta 1000000 pero cuando se hace a un número mayor se tarda más de 24 horas. Cualquier idea sobre cómo acelerar esto / no fuerza bruta. Estoy tratando de contar los triples.
Gracias a Pierre encontré una solución mucho más rápida.
Aquí está mi nuevo código combinado con el de Pierre para cualquiera que lo desee.
def sieve_factors(n): s = [0] * (n+1) s[1] = 1 for i in range(2, n+1, 2): s[i] = 2 for i in range(3, n+1, 2): if s[i] == 0: s[i] = i for j in range(i, n + 1, i): if s[j] == 0: s[j] = i return s Q = sieve_factors(2*(isqrt(2 * 3141592653589793) + 1)) def findfactors(n): global Q yield Q[n] last = Q[n] while n > 1: if Q[n] != last and Q[n] != 1: last = Q[n] yield Q[n] n //= Q[n] def products_of(p_list, upto): for i, p in enumerate(p_list): if p > upto: break yield -p for q in products_of(p_list[i+1:], upto=upto // p): yield -p * q def phi(n, upto=None): if upto is not None and upto < n: cnt = upto p_list = list(findfactors(n)) for q in products_of(p_list, upto): cnt += upto // q if q > 0 else -(upto // -q) return cnt cnt = n for p in findfactors(n): cnt *= (1 - 1/p) return int(cnt) def countprimtrips(n): cnt = 0 for m in range(3, int(sqrt(2*n)) + 1, 2): xmax = int(sqrt(2*n - m**2)) cnt += phi(2*m, upto=xmax) if xmax < m else phi(2*m) // 2 return cnt print(countprimtrips(3141592653589793))Como se mencionó en la respuesta anterior, la mayor parte del tiempo se dedicó a la factorización, así que tomé su código y agregué un tamiz de todos los números hasta x-max, siendo cada número el índice que produce su factor primo más bajo. Encuentra la respuesta en 4 minutos y 44 segundos. (284.6727148 segundos). Gracias por la ayuda Pedro.