GCD를 찾는 Stein의 알고리즘
GfG Practice에서 사용해 보세요. 
산출
산출
스타인의 알고리즘 또는 이진 GCD 알고리즘 음이 아닌 두 정수의 최대 공약수를 계산하는 알고리즘입니다. Stein의 알고리즘은 나눗셈을 산술 이동 비교 및 뺄셈으로 대체합니다.
예:
입력 : a = 17 b = 34
산출 : 17
입력 : a = 50 b = 49
산출 : 1
Stein의 알고리즘 gcd(a b)를 사용하여 GCD를 찾는 알고리즘
알고리즘은 주로 표준에 대한 최적화입니다. GCD에 대한 유클리드 알고리즘
- a와 b가 모두 0이면 gcd는 0입니다. gcd(0 0) = 0입니다.
- gcd(a 0) = a 및 gcd(0 b) = b 왜냐하면 모든 것이 0으로 나누어지기 때문입니다.
- a와 b가 모두 짝수인 경우 gcd(a b) = 2*gcd(a/2 b/2)는 2가 공약수이기 때문입니다. 2와의 곱셈은 비트 시프트 연산자를 사용하여 수행할 수 있습니다.
- a가 짝수이고 b가 홀수이면 gcd(a b) = gcd(a/2 b). 마찬가지로 a가 홀수이고 b가 짝수이면
gcd(ab) = gcd(ab/2). 2는 공약수가 아니기 때문이다. - a와 b가 모두 홀수이면 gcd(a b) = gcd(|a-b|/2 b)입니다. 두 홀수의 차이는 짝수라는 점에 유의하세요.
- a = b 또는 a = 0이 될 때까지 3~5단계를 반복합니다. 두 경우 모두 GCD는 power(2 k) * b입니다. 여기서 power(2 k)는 2의 k 거듭제곱이고 k는 3단계에서 찾은 2의 공통 인자 수입니다.
// Iterative C++ program to // implement Stein's Algorithm #include using namespace std ; // Function to implement // Stein's Algorithm int gcd ( int a int b ) { /* GCD(0 b) == b; GCD(a 0) == a GCD(0 0) == 0 */ if ( a == 0 ) return b ; if ( b == 0 ) return a ; /*Finding K where K is the greatest power of 2 that divides both a and b. */ int k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } /* Dividing a by 2 until a becomes odd */ while (( a & 1 ) == 0 ) a >>= 1 ; /* From here on 'a' is always odd. */ do { /* If b is even remove all factor of 2 in b */ while (( b & 1 ) == 0 ) b >>= 1 ; /* Now a and b are both odd. Swap if necessary so a <= b then set b = b - a (which is even).*/ if ( a > b ) swap ( a b ); // Swap u and v. b = ( b - a ); } while ( b != 0 ); /* restore common factors of 2 */ return a < < k ; } // Driver code int main () { int a = 34 b = 17 ; printf ( 'Gcd of given numbers is %d n ' gcd ( a b )); return 0 ; }
Java // Iterative Java program to // implement Stein's Algorithm import java.io.* ; class GFG { // Function to implement Stein's // Algorithm static int gcd ( int a int b ) { // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // Finding K where K is the greatest // power of 2 that divides both a and b int k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } // Dividing a by 2 until a becomes odd while (( a & 1 ) == 0 ) a >>= 1 ; // From here on 'a' is always odd. do { // If b is even remove // all factor of 2 in b while (( b & 1 ) == 0 ) b >>= 1 ; // Now a and b are both odd. Swap // if necessary so a <= b then set // b = b - a (which is even) if ( a > b ) { // Swap u and v. int temp = a ; a = b ; b = temp ; } b = ( b - a ); } while ( b != 0 ); // restore common factors of 2 return a < < k ; } // Driver code public static void main ( String args [] ) { int a = 34 b = 17 ; System . out . println ( 'Gcd of given ' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by Nikita Tiwari
Python # Iterative Python 3 program to # implement Stein's Algorithm # Function to implement # Stein's Algorithm def gcd ( a b ): # GCD(0 b) == b; GCD(a 0) == a # GCD(0 0) == 0 if ( a == 0 ): return b if ( b == 0 ): return a # Finding K where K is the # greatest power of 2 that # divides both a and b. k = 0 while ((( a | b ) & 1 ) == 0 ): a = a >> 1 b = b >> 1 k = k + 1 # Dividing a by 2 until a becomes odd while (( a & 1 ) == 0 ): a = a >> 1 # From here on 'a' is always odd. while ( b != 0 ): # If b is even remove all # factor of 2 in b while (( b & 1 ) == 0 ): b = b >> 1 # Now a and b are both odd. Swap if # necessary so a <= b then set # b = b - a (which is even). if ( a > b ): # Swap u and v. temp = a a = b b = temp b = ( b - a ) # restore common factors of 2 return ( a < < k ) # Driver code a = 34 b = 17 print ( 'Gcd of given numbers is ' gcd ( a b )) # This code is contributed by Nikita Tiwari.
C# // Iterative C# program to implement // Stein's Algorithm using System ; class GFG { // Function to implement Stein's // Algorithm static int gcd ( int a int b ) { // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // Finding K where K is the greatest // power of 2 that divides both a and b int k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } // Dividing a by 2 until a becomes odd while (( a & 1 ) == 0 ) a >>= 1 ; // From here on 'a' is always odd do { // If b is even remove // all factor of 2 in b while (( b & 1 ) == 0 ) b >>= 1 ; /* Now a and b are both odd. Swap if necessary so a <= b then set b = b - a (which is even).*/ if ( a > b ) { // Swap u and v. int temp = a ; a = b ; b = temp ; } b = ( b - a ); } while ( b != 0 ); /* restore common factors of 2 */ return a < < k ; } // Driver code public static void Main () { int a = 34 b = 17 ; Console . Write ( 'Gcd of given ' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by nitin mittal
JavaScript < script > // Iterative JavaScript program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( a b ) { /* GCD(0 b) == b; GCD(a 0) == a GCD(0 0) == 0 */ if ( a == 0 ) return b ; if ( b == 0 ) return a ; /*Finding K where K is the greatest power of 2 that divides both a and b. */ let k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } /* Dividing a by 2 until a becomes odd */ while (( a & 1 ) == 0 ) a >>= 1 ; /* From here on 'a' is always odd. */ do { /* If b is even remove all factor of 2 in b */ while (( b & 1 ) == 0 ) b >>= 1 ; /* Now a and b are both odd. Swap if necessary so a <= b then set b = b - a (which is even).*/ if ( a > b ){ let t = a ; a = b ; b = t ; } b = ( b - a ); } while ( b != 0 ); /* restore common factors of 2 */ return a < < k ; } // Driver code let a = 34 b = 17 ; document . write ( 'Gcd of given numbers is ' + gcd ( a b )); // This code contributed by gauravrajput1 < /script>
PHP // Iterative php program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( $a $b ) { // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( $a == 0 ) return $b ; if ( $b == 0 ) return $a ; // Finding K where K is the greatest // power of 2 that divides both a and b. $k ; for ( $k = 0 ; (( $a | $b ) & 1 ) == 0 ; ++ $k ) { $a >>= 1 ; $b >>= 1 ; } // Dividing a by 2 until a becomes odd while (( $a & 1 ) == 0 ) $a >>= 1 ; // From here on 'a' is always odd. do { // If b is even remove // all factor of 2 in b while (( $b & 1 ) == 0 ) $b >>= 1 ; // Now a and b are both odd. Swap // if necessary so a <= b then set // b = b - a (which is even) if ( $a > $b ) swap ( $a $b ); // Swap u and v. $b = ( $b - $a ); } while ( $b != 0 ); // restore common factors of 2 return $a < < $k ; } // Driver code $a = 34 ; $b = 17 ; echo 'Gcd of given numbers is ' . gcd ( $a $b ); // This code is contributed by ajit ?>
산출
Gcd of given numbers is 17
시간 복잡도: O(N*N)
보조 공간: 오(1)
[예상 접근방식 2] 재귀적 구현 - O(N*N) 시간과 O(N*N) 공간
C++ // Recursive C++ program to // implement Stein's Algorithm #include using namespace std ; // Function to implement // Stein's Algorithm int gcd ( int a int b ) { if ( a == b ) return a ; // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 if ( ~ a & 1 ) // a is even { if ( b & 1 ) // b is odd return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } if ( ~ b & 1 ) // a is odd b is even return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver code int main () { int a = 34 b = 17 ; printf ( 'Gcd of given numbers is %d n ' gcd ( a b )); return 0 ; }
Java // Recursive Java program to // implement Stein's Algorithm import java.io.* ; class GFG { // Function to implement // Stein's Algorithm static int gcd ( int a int b ) { if ( a == b ) return a ; // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 if (( ~ a & 1 ) == 1 ) // a is even { if (( b & 1 ) == 1 ) // b is odd return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } // a is odd b is even if (( ~ b & 1 ) == 1 ) return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver code public static void main ( String args [] ) { int a = 34 b = 17 ; System . out . println ( 'Gcd of given' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by Nikita Tiwari
Python # Recursive Python 3 program to # implement Stein's Algorithm # Function to implement # Stein's Algorithm def gcd ( a b ): if ( a == b ): return a # GCD(0 b) == b; GCD(a 0) == a # GCD(0 0) == 0 if ( a == 0 ): return b if ( b == 0 ): return a # look for factors of 2 # a is even if (( ~ a & 1 ) == 1 ): # b is odd if (( b & 1 ) == 1 ): return gcd ( a >> 1 b ) else : # both a and b are even return ( gcd ( a >> 1 b >> 1 ) < < 1 ) # a is odd b is even if (( ~ b & 1 ) == 1 ): return gcd ( a b >> 1 ) # reduce larger number if ( a > b ): return gcd (( a - b ) >> 1 b ) return gcd (( b - a ) >> 1 a ) # Driver code a b = 34 17 print ( 'Gcd of given numbers is ' gcd ( a b )) # This code is contributed # by Nikita Tiwari.
C# // Recursive C# program to // implement Stein's Algorithm using System ; class GFG { // Function to implement // Stein's Algorithm static int gcd ( int a int b ) { if ( a == b ) return a ; // GCD(0 b) == b; // GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 // a is even if (( ~ a & 1 ) == 1 ) { // b is odd if (( b & 1 ) == 1 ) return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } // a is odd b is even if (( ~ b & 1 ) == 1 ) return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver code public static void Main () { int a = 34 b = 17 ; Console . Write ( 'Gcd of given' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by nitin mittal.
JavaScript < script > // JavaScript program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( a b ) { if ( a == b ) return a ; // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 if (( ~ a & 1 ) == 1 ) // a is even { if (( b & 1 ) == 1 ) // b is odd return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } // a is odd b is even if (( ~ b & 1 ) == 1 ) return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver Code let a = 34 b = 17 ; document . write ( 'Gcd of given ' + 'numbers is ' + gcd ( a b )); < /script>
PHP // Recursive PHP program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( $a $b ) { if ( $a == $b ) return $a ; /* GCD(0 b) == b; GCD(a 0) == a GCD(0 0) == 0 */ if ( $a == 0 ) return $b ; if ( $b == 0 ) return $a ; // look for factors of 2 if ( ~ $a & 1 ) // a is even { if ( $b & 1 ) // b is odd return gcd ( $a >> 1 $b ); else // both a and b are even return gcd ( $a >> 1 $b >> 1 ) < < 1 ; } if ( ~ $b & 1 ) // a is odd b is even return gcd ( $a $b >> 1 ); // reduce larger number if ( $a > $b ) return gcd (( $a - $b ) >> 1 $b ); return gcd (( $b - $a ) >> 1 $a ); } // Driver code $a = 34 ; $b = 17 ; echo 'Gcd of given numbers is: ' gcd ( $a $b ); // This code is contributed by aj_36 ?>
산출
Gcd of given numbers is 17
시간 복잡도 : O(N*N) 여기서 N은 더 큰 숫자의 비트 수입니다.
보조 공간: O(N*N) 여기서 N은 더 큰 숫자의 비트 수입니다.
당신은 또한 좋아할 수도 있습니다 - 기본 및 확장 유클리드 알고리즘
유클리드의 GCD 알고리즘에 비해 장점
- Stein의 알고리즘은 Euclid의 GCD 알고리즘의 최적화된 버전입니다.
- 비트 시프트 연산자를 사용하면 더 효율적입니다.
![인구 순위 기준 미국에서 가장 큰 10대 도시 [업데이트된 목록 2024]](https://techcodeview.com/img/us-gk/09/top-10-largest-cities-united-states-population-ranked.webp)
