# factorization

## Pythagorean Triple Problem in Sub-linear Time

The Pythagorean triple problem is as follows. Given an input integer $$n$$, return integers $$a$$, $$b$$, $$c$$ such that the two following conditions hold: $$a b c = n$$ $$a^2 + b^2 = c^2$$ I was interested in finding a solution to this problem that was both succint and had good asymptotic complexity. The solution I found runs in O(sqrt(n)) time by deconstructing the problem into the well-known 3SUM problem.