This paper presents an algorithm for factoring integers based on a factoring technique due to Euler. When factorization fails, the input is proved to be prime. Omitting details and special cases, the idea is to write an integer \(n\) in two ways: \(n=x^2_0+d\) and \(an= x^2_1+ dy^2_1\), where \(x_0, x_1, y_1, a,d\) are integers. One then hopes that \(\text{gcd} (n,x_0 y_1 - x_1)\) yields a proper factor of \(n\). The algorithm is explained clearly with examples, it is proven correct, and an \(O(n^{1/3 + \varepsilon})\) running time is proven.