Euler 's Factorization method |  ; Recursive function to return gcd of a and b ; Function to return N as the sum of two squares in two possible ways ; Iterate a loop from 1 to Math . sqrt ( n ) ; If i * i is square check if there exists another integer such that h is a perfect square and i * i + h = n ; If h is perfect square ; Store in the sorted way ; If there is already a pair check if pairs are equal or not ; Insert the first pair ; If two pairs are found ; Function to find the factors ; Get pairs where a ^ 2 + b ^ 2 = n ; Number cannot be represented as sum of squares in two ways ; Assign a , b , c , d ; Swap if a < c because if a - c < 0 , GCD cant be computed . ; Compute the values of k , h , l , m using the formula mentioned in the approach ; Print the values of a , b , c , d and k , l , m , h ; Printing the factors ; Driver code
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } function sumOfSquares ( n , vp ) { for ( let i = 1 ; i <= Math . sqrt ( n ) ; i ++ ) { let h = n - i * i , h1 = Math . floor ( Math . sqrt ( h ) ) ; if ( h1 * h1 == h ) { let a = Math . max ( h1 , i ) , b = Math . min ( h1 , i ) ; if ( vp . length == 1 && a != vp [ 0 ] . first ) vp . push ( new pair ( a , b ) ) ; if ( vp . length == 0 ) vp . push ( new pair ( a , b ) ) ; if ( vp . length == 2 ) return ; } } } function findFactors ( n ) { let vp = [ ] ; sumOfSquares ( n , vp ) ; if ( vp . length != 2 ) document . write ( " " ) ; let a , b , c , d ; a = vp [ 0 ] . first ; b = vp [ 0 ] . second ; c = vp [ 1 ] . first ; d = vp [ 1 ] . second ; if ( a < c ) { let t = a ; a = c ; c = t ; t = b ; b = d ; d = t ; } let k , h , l , m ; k = __gcd ( a - c , d - b ) ; h = __gcd ( a + c , d + b ) ; l = ( a - c ) / k ; m = ( d - b ) / k ; document . write ( " " + a + " " + ( a - c ) + " " + k + " " ) ; document . write ( " " + b + " " + ( a + c ) + " " + h + " " ) ; document . write ( " " + c + " " + ( d - b ) + " " + l + " " ) ; document . write ( " " + d + " " + ( d + b ) + " " + m + " " ) ; if ( k % 2 == 0 && h % 2 == 0 ) { k = k / 2 ; h = h / 2 ; document . write ( " " + ( ( k ) * ( k ) + ( h ) * ( h ) ) + " " + ( l * l + m * m ) + " " ) ; } else { l = l / 2 ; m = m / 2 ; document . write ( " " + ( ( l ) * ( l ) + ( m ) * ( m ) ) + " " + ( k * k + h * h ) + " " ) ; } } let n = 100000 ; findFactors ( n ) ;