title: Speeding up the loops or different ideas for counting primitive triples
body: <pre><code>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 &lt; n:
                      i += 1
      end = time.time()
      return i, end-start
  print(pythag_triples(3141592653589793))
  </code></pre>
  <p>I'm trying to calculate primitive pythagorean triples using the idea that all triples are generated from using m, n that are both odd and coprime. I already know that the function works up to 1000000 but when doing it to the larger number its taken longer than 24 hours. Any ideas on how to speed this up/ not brute force it. I am trying to count the triples.</p>