两个数的HCF（最高公因数）或GCD（最大公因数）是将两个数相除的最大数。
null
例如，20和28的GCD为4，98和56的GCD为14。
A. 简单解决方案 就是 找出所有的主要因素 然后找出两个数中所有因子的交集。最后返回相交元素的乘积。
一 有效解决方案 就是使用 欧几里德算法 这是用于此目的的主要算法。这个想法是，如果从较大的数字中减去较小的数字，两个数字的GCD不会改变。
C++
// C++ program to find GCD of two numbers #include <iostream> using namespace std; // Recursive function to return gcd of a and b int gcd( int a, int b) { // Everything divides 0 if (a == 0 && b == 0) return 0; if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver program to test above function int main() { int a = 0, b = 56; cout << "GCD of " << a << " and " << b << " is " << gcd(a, b); return 0; } // This code is contributed by shivanisinghss2110 |
C
// C program to find GCD of two numbers #include <stdio.h> // Recursive function to return gcd of a and b int gcd( int a, int b) { // Everything divides 0 if (a == 0 && b == 0) return 0; if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver program to test above function int main() { int a = 0, b = 56; printf ( "GCD of %d and %d is %d " , a, b, gcd(a, b)); return 0; } |
JAVA
// Java program to find GCD of two numbers class Test { // Recursive function to return gcd of a and b static int gcd( int a, int b) { // Everything divides 0 if (a == 0 && b == 0 ) return 0 ; if (a == 0 ) return b; if (b == 0 ) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver method public static void main(String[] args) { int a = 98 , b = 56 ; System.out.println( "GCD of " + a + " and " + b + " is " + gcd(a, b)); } } |
Python3
# Recursive function to return gcd of a and b def gcd(a, b): # Everything divides 0 if (a = = 0 and b = = 0 ): return 0 if (a = = 0 ): return b if (b = = 0 ): return a # base case if (a = = b): return a # a is greater if (a > b): return gcd(a - b, b) return gcd(a, b - a) # Driver program to test above function a = 98 b = 56 if (gcd(a, b)): print ( 'GCD of' , a, 'and' , b, 'is' , gcd(a, b)) else : print ( 'not found' ) # This code is contributed by Danish Raza |
C#
// C# program to find GCD of two // numbers using System; class GFG { // Recursive function to return // gcd of a and b static int gcd( int a, int b) { // Everything divides 0 if (a == 0 && b == 0) return 0; if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver method public static void Main() { int a = 98, b = 56; Console.WriteLine( "GCD of " + a + " and " + b + " is " + gcd(a, b)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to find GCD // of two numbers // Recursive function to // return gcd of a and b function gcd( $a , $b ) { // Everything divides 0 if ( $a ==0 && $b ==0) return 0 ; if ( $a == 0) return $b ; if ( $b == 0) return $a ; // base case if ( $a == $b ) return $a ; // a is greater if ( $a > $b ) return gcd( $a - $b , $b ) ; return gcd( $a , $b - $a ) ; } // Driver code $a = 98 ; $b = 56 ; echo "GCD of $a and $b is " , gcd( $a , $b ) ; // This code is contributed by Anivesh Tiwari ?> |
Javascript
<script> // Javascript program to find GCD of two numbers // Recursive function to return gcd of a and b function gcd(a, b) { // Everything divides 0 if (a == 0 && b == 0) return 0; if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Driver code var a = 98, b = 56; document.write( "GCD of " + a + " and " + b + " is " + gcd(a, b)); // This code is contributed by noob2000 </script> |
输出：
GCD of 98 and 56 is 14
A. 更有效的解决方案 是用模运算符 欧几里德算法 .
C++
// C++ program to find GCD of two numbers #include <iostream> using namespace std; // Recursive function to return gcd of a and b int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver program to test above function int main() { int a = 98, b = 56; cout<< "GCD of " <<a << " and " << b << " is " << gcd(a, b); return 0; } // This code is contributed by shivanisinghss2110 |
C
// C program to find GCD of two numbers #include <stdio.h> // Recursive function to return gcd of a and b int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver program to test above function int main() { int a = 98, b = 56; printf ( "GCD of %d and %d is %d " , a, b, gcd(a, b)); return 0; } |
JAVA
// Java program to find GCD of two numbers class Test { // Recursive function to return gcd of a and b static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Driver method public static void main(String[] args) { int a = 98 , b = 56 ; System.out.println( "GCD of " + a + " and " + b + " is " + gcd(a, b)); } } |
Python3
# Recursive function to return gcd of a and b def gcd(a,b): # Everything divides 0 if (b = = 0 ): return a return gcd(b, a % b) # Driver program to test above function a = 98 b = 56 if (gcd(a, b)): print ( 'GCD of' , a, 'and' , b, 'is' , gcd(a, b)) else : print ( 'not found' ) # This code is contributed by Danish Raza |
C#
// C# program to find GCD of two // numbers using System; class GFG { // Recursive function to return // gcd of a and b static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver method public static void Main() { int a = 98, b = 56; Console.WriteLine( "GCD of " + a + " and " + b + " is " + gcd(a, b)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to find GCD // of two numbers // Recursive function to // return gcd of a and b function gcd( $a , $b ) { // Everything divides 0 if ( $b ==0) return $a ; return gcd( $b , $a % $b ) ; } // Driver code $a = 98 ; $b = 56 ; echo "GCD of $a and $b is " , gcd( $a , $b ) ; // This code is contributed by Anivesh Tiwari ?> |
Javascript
<script> // Javascript program to find GCD of two numbers // Recursive function to return gcd of a and b function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Driver code var a = 98, b = 56; document.write( "GCD of " + a + " and " + b + " is " + gcd(a, b)); // This code is contributed by Ankita saini </script> |
输出：
GCD of 98 and 56 is 14
请参考 两个以上（或数组）数的GCD 查找两个以上数字的HCF。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
