两个以上（或数组）数的GCD-yiteyi-C++库

给定一个数字数组，找到数组元素的GCD。在之前的帖子中，我们找到两个数字的GCD . 例如：

null

Input  : arr[] = {1, 2, 3}Output : 1Input  : arr[] = {2, 4, 6, 8}Output : 2

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

三个或三个以上数字的GCD等于所有数字共有的素数因子的乘积，但也可以通过重复计算成对数字的GCD来计算。

gcd(a, b, c) = gcd(a, gcd(b, c))              = gcd(gcd(a, b), c)              = gcd(gcd(a, c), b)

对于元素数组，我们执行以下操作。我们还将检查结果，如果任何步骤的结果变为1，我们将只返回1作为gcd（1，x）=1。

result = arr[0]For i = 1 to n-1   result = GCD(result, arr[i])

下面是上述想法的实施。

C++

                         // C++ program to find GCD of two or                       
                         // more numbers                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to return gcd of a and b                       
                         int                                     gcd(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 if                                     (a == 0)                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                         }                       
           
                         // Function to find gcd of array of                       
                         // numbers                       
                         int                                     findGCD(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     result = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 result = gcd(arr[i], result);                       
           
                                                 if                                     (result == 1)                       
                                                 {                       
                                                 return                                     1;                       
                                                 }                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 4, 6, 8, 16 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << findGCD(arr, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find GCD of two or                       
                         // more numbers                       
           
                         public                                     class                                     GCD {                       
                                                 // Function to return gcd of a and b                       
                                                 static                                     int                                     gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 if                                     (a ==                                     0                                     )                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                                                 }                       
           
                                                 // Function to find gcd of array of                       
                                                 // numbers                       
                                                 static                                     int                                     findGCD(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     result = arr[                                     0                                     ];                       
                                                 for                                     (                                     int                                     element: arr){                       
                                                 result = gcd(result, element);                       
           
                                                 if                                     (result ==                                     1                                     )                       
                                                 {                       
                                                 return                                     1                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 return                                     result;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     8                                     ,                                     16                                     };                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println(findGCD(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Saket Kumar                       

python

                         # GCD of more than two (or array) numbers                       
           
                         # Function implements the Euclidian                       
                         # algorithm to find H.C.F. of two number                       
                         def                                     find_gcd(x, y):                       
                                   
                                                 while                                     (y):                       
                                                 x, y                                     =                                     y, x                                     %                                     y                       
                                   
                                                 return                                     x                       
                                   
                         # Driver Code                       
                         l                                     =                                     [                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     8                                     ,                                     16                                     ]                       
           
                         num1                                     =                                     l[                                     0                                     ]                       
                         num2                                     =                                     l[                                     1                                     ]                       
                         gcd                                     =                                     find_gcd(num1, num2)                       
           
                         for                                     i                                     in                                     range                                     (                                     2                                     ,                                     len                                     (l)):                       
                                                 gcd                                     =                                     find_gcd(gcd, l[i])                       
                                   
                         print                                     (gcd)                       
           
                         # Code contributed by Mohit Gupta_OMG                       

C#

                         // C# program to find GCD of                       
                         // two or more numbers                       
                         using                                     System;                       
           
                         public                                     class                                     GCD {                       
                                   
                                                 // Function to return gcd of a and b                       
                                                 static                                     int                                     gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 if                                     (a == 0)                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                                                 }                       
           
                                                 // Function to find gcd of                       
                                                 // array of numbers                       
                                                 static                                     int                                     findGCD(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 int                                     result = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++){                       
                                                 result = gcd(arr[i], result);                       
           
                                                 if                                     (result == 1)                       
                                                 {                       
                                                 return                                     1;                       
                                                 }                       
                                                 }                       
           
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 2, 4, 6, 8, 16 };                       
                                                 int                                     n = arr.Length;                       
                                                 Console.Write(findGCD(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal                       

PHP

                         <?php                       
                         // PHP program to find GCD of two or                       
                         // more numbers                       
           
                         // Function to return gcd of a and b                       
                         function                                     gcd(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 if                                     (                                     $a                                     == 0)                       
                                                 return                                     $b                                     ;                       
                                                 return                                     gcd(                                     $b                                     %                                     $a                                     ,                                     $a                                     );                       
                         }                       
           
                         // Function to find gcd of array of                       
                         // numbers                       
                         function                                     findGCD(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $result                                     =                                     $arr                                     [0];                       
           
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++){                       
                                                 $result                                     = gcd(                                     $arr                                     [                                     $i                                     ],                                     $result                                     );                       
           
                                                 if                                     (                                     $result                                     == 1)                       
                                                 {                       
                                                 return                                     1;                       
                                                 }                       
                                                 }                       
                                                 return                                     $result                                     ;                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     ( 2, 4, 6, 8, 16 );                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         echo                                     (findGCD(                                     $arr                                     ,                                     $n                                     ));                       
           
                         // This code is contributed by                       
                         // Prasad Kshirsagar.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find GCD of two or                       
                         // more numbers                       
           
                         // Function to return gcd of a and b                       
                         function                                     gcd(a, b)                       
                         {                       
                                                 if                                     (a == 0)                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                         }                       
           
                         // Function to find gcd of array of                       
                         // numbers                       
                         function                                     findGCD(arr, n)                       
                         {                       
                                                 let result = arr[0];                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 {                       
                                                 result = gcd(arr[i], result);                       
           
                                                 if                                     (result == 1)                       
                                                 {                       
                                                 return                                     1;                       
                                                 }                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
           
                                                 let arr = [ 2, 4, 6, 8, 16 ];                       
                                                 let n = arr.length;                       
                                                 document.write(findGCD(arr, n) +                                     "<br>"                                     );                       
           
                         // This is code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

时间复杂性： O（N*log（N）），其中N是数组的最大元素 辅助空间： O（1）

递归方法： 算法的递归实现：

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // recursive implementation                       
                         int                                     GcdOfArray(vector<                                     int                                     >& arr,                                     int                                     idx)                       
                         {                       
                                                 if                                     (idx == arr.size() - 1) {                       
                                                 return                                     arr[idx];                       
                                                 }                       
                                                 int                                     a = arr[idx];                       
                                                 int                                     b = GcdOfArray(arr, idx + 1);                       
                                                 return                                     __gcd(                       
                                                 a, b);                                     // __gcd(a,b) is inbuilt library function                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 vector<                                     int                                     > arr = { 1, 2, 3 };                       
                                                 cout << GcdOfArray(arr, 0) <<                                     ""                                     ;                       
           
                                                 arr = { 2, 4, 6, 8 };                       
                                                 cout << GcdOfArray(arr, 0) <<                                     ""                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         import                                     java.util.*;                       
                         class                                     GFG                       
                         {                       
                                   
                                                 // Recursive function to return gcd of a and b                       
                                                 static                                     int                                     __gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     b ==                                     0                                     ? a:__gcd(b, a % b);                       
                                                 }                       
                                   
                         // recursive implementation                       
                         static                                     int                                     GcdOfArray(                                     int                                     [] arr,                                     int                                     idx)                       
                         {                       
                                                 if                                     (idx == arr.length -                                     1                                     ) {                       
                                                 return                                     arr[idx];                       
                                                 }                       
                                                 int                                     a = arr[idx];                       
                                                 int                                     b = GcdOfArray(arr, idx +                                     1                                     );                       
                                                 return                                     __gcd(                       
                                                 a, b);                                     // __gcd(a,b) is inbuilt library function                       
                         }                       
           
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     [] arr = {                                     1                                     ,                                     2                                     ,                                     3                                     };                       
                                                 System.out.print(GcdOfArray(arr,                                     0                                     )+                                     ""                                     );                       
           
                                                 int                                     [] arr1 = {                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     8                                     };                       
                                                 System.out.print(GcdOfArray(arr1,                                     0                                     )+                                     ""                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by gauravrajput1                       

输出

时间复杂性： O（N*log（N）），其中N是数组的最大元素

辅助空间 ：O（N）

本文由 丹麦拉扎 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章