Primitive Right Triangles — Solution & Editorial

Back to the Problem

Euclid's parametrization: primitive triples come from coprime m > k > 0 of opposite parity, with c = m² + k². Enumerate such (m, k) with m² ≤ N.

Complexity: O(√N · √N) = O(N)