Euler 's Factorization method | C ++ program to implement Eulers Factorization algorithm ; Function to return N as the sum of two squares in two possible ways ; Iterate a loop from 1 to 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void sumOfSquares ( int n , vector < pair < int , int > > & vp ) { for ( int i = 1 ; i <= sqrt ( n ) ; i ++ ) { int h = n - i * i , h1 = sqrt ( h ) ; if ( h1 * h1 == h ) { int a = max ( h1 , i ) , b = min ( h1 , i ) ; if ( vp . size ( ) == 1 && a != vp [ 0 ] . first ) vp . push_back ( make_pair ( a , b ) ) ; if ( vp . size ( ) == 0 ) vp . push_back ( make_pair ( a , b ) ) ; if ( vp . size ( ) == 2 ) return ; } } } void findFactors ( int n ) { vector < pair < int , int > > vp ; sumOfSquares ( n , vp ) ; if ( vp . size ( ) != 2 ) cout << " Factors ▁ Not ▁ Possible " ; int a , b , c , d ; a = vp [ 0 ] . first ; b = vp [ 0 ] . second ; c = vp [ 1 ] . first ; d = vp [ 1 ] . second ; if ( a < c ) { int t = a ; a = c ; c = t ; t = b ; b = d ; d = t ; } int k , h , l , m ; k = __gcd ( a - c , d - b ) ; h = __gcd ( a + c , d + b ) ; l = ( a - c ) / k ; m = ( d - b ) / k ; cout << " a ▁ = ▁ " << a << " TABSYMBOL TABSYMBOL ( A ) ▁ a ▁ - ▁ c ▁ = ▁ " << ( a - c ) << " TABSYMBOL TABSYMBOL k ▁ = ▁ gcd [ A , ▁ C ] ▁ = ▁ " << k << endl ; cout << " b ▁ = ▁ " << b << " TABSYMBOL TABSYMBOL ( B ) ▁ a ▁ + ▁ c ▁ = ▁ " << ( a + c ) << " TABSYMBOL TABSYMBOL h ▁ = ▁ gcd [ B , ▁ D ] ▁ = ▁ " << h << endl ; cout << " c ▁ = ▁ " << c << " TABSYMBOL TABSYMBOL ( C ) ▁ d ▁ - ▁ b ▁ = ▁ " << ( d - b ) << " TABSYMBOL TABSYMBOL l ▁ = ▁ A / k ▁ = ▁ " << l << endl ; cout << " d ▁ = ▁ " << d << " TABSYMBOL TABSYMBOL ( D ) ▁ d ▁ + ▁ b ▁ = ▁ " << ( d + b ) << " TABSYMBOL TABSYMBOL m ▁ = ▁ c / k ▁ = ▁ " << m << endl ; if ( k % 2 == 0 && h % 2 == 0 ) { k = k / 2 ; h = h / 2 ; cout << " Factors ▁ are : ▁ " << ( ( k ) * ( k ) + ( h ) * ( h ) ) << " ▁ " << ( l * l + m * m ) << endl ; } else { l = l / 2 ; m = m / 2 ; cout << " Factors ▁ are : ▁ " << ( ( l ) * ( l ) + ( m ) * ( m ) ) << " ▁ " << ( k * k + h * h ) << endl ; } } int main ( ) { int n = 100000 ; findFactors ( n ) ; return 0 ; }