Stein 's Algorithm for finding GCD | Recursive C ++ program to implement Stein 's Algorithm ; Function to implement Stein 's Algorithm ; GCD ( 0 , b ) == b ; GCD ( a , 0 ) == a , GCD ( 0 , 0 ) == 0 ; look for factors of 2 if ( ~ a & 1 ) a is even ; if ( b & 1 ) b is odd ; else both a and b are even ; if ( ~ b & 1 ) a is odd , b is even ; reduce larger number ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( a == b ) return a ; if ( a == 0 ) return b ; if ( b == 0 ) return a ; { return gcd ( a >> 1 , b ) ; return gcd ( a >> 1 , b >> 1 ) << 1 ; } return gcd ( a , b >> 1 ) ; if ( a > b ) return gcd ( ( a - b ) >> 1 , b ) ; return gcd ( ( b - a ) >> 1 , a ) ; } int main ( ) { int a = 34 , b = 17 ; printf ( " Gcd ▁ of ▁ given ▁ numbers ▁ is ▁ % d STRNEWLINE " , gcd ( a , b ) ) ; return 0 ; }