我们得到一个正整数数组。在阵列中找到GCD最大的配对。 例如：
null
Input : arr[] : { 1 2 3 4 5 }Output : 2Explanation : Pair {2, 4} has GCD 2 which is highest. Other pairs have a GCD of 1.Input : arr[] : { 2 3 4 8 8 11 12 }Output : 8Explanation : Pair {8, 8} has GCD 8 which is highest.
方法1（暴力） ：解决此问题的最简单方法是使用两个循环来生成数组中所有可能的元素对，并计算和比较 GCD 同时我们可以使用 德演算法 用于高效计算两个数字的GCD。 时间复杂性 ：O（N^2*log（最大（a，b））） 这里，log（max（a，b））是计算a和b的GCD的时间复杂度。 方法2：（高效） 在这种方法中，我们维护一个计数数组来存储每个元素的除数计数。我们将遍历给定的数组，对于每个元素，我们将计算其除数和计数数组索引处的增量。计算除数的过程将花费O（sqrt（arr[i]）时间，其中arr[i]是给定数组中索引i处的元素。在整个遍历之后，我们可以简单地将计数数组从最后一个索引遍历到索引1。如果我们发现一个索引的值大于1，那么这意味着它是2个元素的除数，也是最大GCD。 以下是上述方法的实施情况：
C++
// C++ Code to find pair with // maximum GCD in an array #include <bits/stdc++.h> using namespace std; // function to find GCD of pair with // max GCD in the array int findMaxGCD( int arr[], int n) { // Computing highest element int high = 0; for ( int i = 0; i < n; i++) high = max(high, arr[i]); // Array to store the count of divisors // i.e. Potential GCDs int divisors[high + 1] = { 0 }; // Iterating over every element for ( int i = 0; i < n; i++) { // Calculating all the divisors for ( int j = 1; j <= sqrt (arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count for divisor divisors[j]++; // Element/divisor is also a divisor // Checking if both divisors are // not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest potential GCD for ( int i = high; i >= 1; i--) // If this divisor can divide at least 2 // numbers, it is a GCD of at least 1 pair if (divisors[i] > 1) return i; } // Driver code int main() { // Array in which pair with max GCD // is to be found int arr[] = { 1, 2, 4, 8, 8, 12 }; // Size of array int n = sizeof (arr) / sizeof (arr[0]); cout << findMaxGCD(arr,n); return 0; } |
JAVA
// JAVA Code for Find pair with maximum GCD in an array class GFG { // function to find GCD of pair with // max GCD in the array public static int findMaxGCD( int arr[], int n) { // Computing highest element int high = 0 ; for ( int i = 0 ; i < n; i++) high = Math.max(high, arr[i]); // Array to store the count of divisors // i.e. Potential GCDs int divisors[] = new int [high + 1 ]; // Iterating over every element for ( int i = 0 ; i < n; i++) { // Calculating all the divisors for ( int j = 1 ; j <= Math.sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0 ) { // Incrementing count for divisor divisors[j]++; // Element/divisor is also a divisor // Checking if both divisors are // not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest potential GCD for ( int i = high; i >= 1 ; i--) // If this divisor can divide at least 2 // numbers, it is a GCD of at least 1 pair if (divisors[i] > 1 ) return i; return 1 ; } /* Driver program to test above function */ public static void main(String[] args) { // Array in which pair with max GCD // is to be found int arr[] = { 1 , 2 , 4 , 8 , 8 , 12 }; // Size of array int n = arr.length; System.out.println(findMaxGCD(arr,n)); } } // This code is contributed by Arnav Kr. Mandal. |
python
# Python program to Find pair with # maximum GCD in an array import math # function to find GCD of pair with # max GCD in the array def findMaxGCD(arr, n) : # Computing highest element high = 0 i = 0 while i < n : high = max (high, arr[i]) i = i + 1 # Array to store the count of divisors # i.e. Potential GCDs divisors = [ 0 ] * (high + 1 ) # Iterating over every element i = 0 while i < n : # Calculating all the divisors j = 1 while j < = math.sqrt(arr[i]) : # Divisor found if (arr[i] % j = = 0 ) : # Incrementing count for divisor divisors[j] = divisors[j] + 1 # Element/divisor is also a divisor # Checking if both divisors are # not same if (j ! = arr[i] / j) : divisors[arr[i] / j] = divisors[arr[i] / j] + 1 j = j + 1 i = i + 1 # Checking the highest potential GCD i = high while i > = 1 : # If this divisor can divide at least 2 # numbers, it is a GCD of at least 1 pair if (divisors[i] > 1 ) : return i i = i - 1 return 1 # Driver code # Array in which pair with max GCD # is to be found arr = [ 1 , 2 , 4 , 8 , 8 , 12 ] # Size of array n = len (arr) print findMaxGCD(arr,n) # This code is contributed by Nikita Tiwari. |
C#
// C# Code for Find pair with // maximum GCD in an array using System; class GFG { // Function to find GCD of pair // with max GCD in the array public static int findMaxGCD( int []arr, int n) { // Computing highest element int high = 0; for ( int i = 0; i < n; i++) high = Math.Max(high, arr[i]); // Array to store the count of // divisors i.e. Potential GCDs int []divisors = new int [high + 1]; // Iterating over every element for ( int i = 0; i < n; i++) { // Calculating all the divisors for ( int j = 1; j <= Math.Sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count // for divisor divisors[j]++; // Element / divisor is also // a divisor Checking if both // divisors are not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest potential GCD for ( int i = high; i >= 1; i--) // If this divisor can divide at // least 2 numbers, it is a // GCD of at least 1 pair if (divisors[i] > 1) return i; return 1; } // Driver Code public static void Main(String []args) { // Array in which pair with // max GCD is to be found int []arr = {1, 2, 4, 8, 8, 12}; // Size of array int n = arr.Length; Console.WriteLine(findMaxGCD(arr,n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Code for Find pair with // maximum GCD in an array // Function to find GCD // of pair with max GCD // in the array function findMaxGCD( $arr , $n ) { // Computing highest element $high = 0; for ( $i = 0; $i < $n ; $i ++) $high = max( $high , $arr [ $i ]); // Array to store the // count of divisors // i.e. Potential GCDs $divisors = array_fill (0, $high + 1, 0); // Iterating over every element for ( $i = 0; $i < $n ; $i ++) { // Calculating all // the divisors for ( $j = 1; $j <= (int)(sqrt( $arr [ $i ])); $j ++) { // Divisor found if ( $arr [ $i ] % $j == 0) { // Incrementing count // for divisor $divisors [ $j ]++; // Element/divisor is also // a divisor Checking if // both divisors are not same if ( $j != (int)( $arr [ $i ] / $j )) $divisors [(int)( $arr [ $i ] / $j )]++; } } } // Checking the highest // potential GCD for ( $i = $high ; $i >= 1; $i --) // If this divisor can divide // at least 2 numbers, it is // a GCD of at least 1 pair if ( $divisors [ $i ] > 1) return $i ; } // Driver code // Array in which pair // with max GCD is to // be found $arr = array ( 1, 2, 4, 8, 8, 12 ); // Size of array $n = sizeof( $arr ); echo findMaxGCD( $arr , $n ); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript Code for Find pair with // maximum GCD in an array // function to find GCD of pair with // max GCD in the array function findMaxGCD(arr , n) { // Computing highest element var high = 0; for ( var i = 0; i < n; i++) high = Math.max(high, arr[i]); // Array to store the count of divisors // i.e. Potential GCDs var divisors = Array.from({length: high + 1}, (_, i) => 0); // Iterating over every element for ( var i = 0; i < n; i++) { // Calculating all the divisors for ( var j = 1; j <= Math.sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count for divisor divisors[j]++; // Element/divisor is also a divisor // Checking if both divisors are // not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest potential GCD for ( var i = high; i >= 1; i--) // If this divisor can divide at least 2 // numbers, it is a GCD of at least 1 pair if (divisors[i] > 1) return i; return 1; } /* Driver program to test above function */ // Array in which pair with max GCD // is to be found var arr = [ 1, 2, 4, 8, 8, 12 ]; // Size of array var n = arr.length; document.write(findMaxGCD(arr,n)); // This code contributed by shikhasingrajput </script> |
输出：
8
时间复杂性 ：O（N*sqrt（arr[i]）+H），其中arr[i]表示数组的元素，H表示数组的最大数目。 方法3（最有效） ：这种方法基于 埃拉托斯坦筛 . 首先让我们解决一个更简单的问题，给定一个值X，我们必须判断一对的GCD是否等于X。这可以通过检查数组中有多少元素是X的倍数来实现。如果这样的倍数大于1，那么X将是某对的GCD。 现在，对于GCD最大的配对，我们维护原始数组的计数数组。我们的方法基于上述问题，采用类似筛子的循环方法。下面是这种方法的逐步算法：
- 将“i”从MAX（最大数组元素）迭代到1。
- 将“j”从“i”迭代到“MAX”。我们将检查索引“j”处的计数数组是否为1。
- 每次用“i”增加索引“j”。这样，我们就可以检查 i、 2i、3i等等。
- 如果我们在计数数组中得到两次1，这意味着 2倍的i 存在。这使它成为最高的GCD。
以下是上述方法的实施情况：
C++
// C++ Code to // Find pair with // maximum GCD in // an array #include <bits/stdc++.h> using namespace std; // function to find // GCD of pair with // max GCD in the // array int findMaxGCD( int arr[], int n) { // Calculating MAX in array int high = 0; for ( int i = 0; i < n; i++) high = max(high, arr[i]); // Maintaining count array int count[high + 1] = {0}; for ( int i = 0; i < n; i++) count[arr[i]]++; // Variable to store the // multiples of a number int counter = 0; // Iterating from MAX to 1 // GCD is always between // MAX and 1. The first // GCD found will be the // highest as we are // decrementing the potential // GCD for ( int i = high; i >= 1; i--) { int j = i; counter = 0; // Iterating from current // potential GCD // till it is less than // MAX while (j <= high) { // A multiple found if (count[j] >=2) return j; else if (count[j] == 1) counter++; // Incrementing potential // GCD by itself // To check i, 2i, 3i.... j += i; // 2 multiples found, // max GCD found if (counter == 2) return i; } } } // Driver code int main() { // Array in which pair // with max GCD is to // be found int arr[] = { 1, 2, 4, 8, 8, 12 }; // Size of array int n = sizeof (arr) / sizeof (arr[0]); cout << findMaxGCD(arr, n); return 0; } |
JAVA
// Java Code to // Find pair with // maximum GCD in // an array class GFG { // function to find // GCD of pair with // max GCD in the // array public static int findMaxGCD( int arr[], int n) { // Calculating MAX in // array int high = 0 ; for ( int i = 0 ; i < n; i++) high = Math.max(high, arr[i]); // Maintaining count array int count[]= new int [high + 1 ]; for ( int i = 0 ; i < n; i++) count[arr[i]]++; // Variable to store // the multiples of // a number int counter = 0 ; // Iterating from MAX // to 1 GCD is always // between MAX and 1 // The first GCD found // will be the highest // as we are decrementing // the potential GCD for ( int i = high; i >= 1 ; i--) { int j = i; // Iterating from current // potential GCD till it // is less than MAX while (j <= high) { // A multiple found if (count[j]> 0 ) counter+=count[j]; // Incrementing potential // GCD by itself // To check i, 2i, 3i.... j += i; // 2 multiples found, // max GCD found if (counter == 2 ) return i; } counter= 0 ; } return 1 ; } /* Driver program to test above function */ public static void main(String[] args) { // Array in which pair // with max GCD is to // be found int arr[] = { 1 , 2 , 4 , 8 , 8 , 12 }; // Size of array int n = arr.length; System.out.println(findMaxGCD(arr,n)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 Code to # Find pair with # maximum GCD in # an array # function to find # GCD of pair with # max GCD in the # array def findMaxGCD(arr, n) : # Calculating MAX in # array high = 0 for i in range ( 0 , n) : high = max (high, arr[i]) # Maintaining count array count = [ 0 ] * (high + 1 ) for i in range ( 0 , n) : count[arr[i]] + = 1 # Variable to store the # multiples of a number counter = 0 # Iterating from MAX # to 1 GCD is always # between MAX and 1 # The first GCD found # will be the highest # as we are decrementing # the potential GCD for i in range (high, 0 , - 1 ) : j = i # Iterating from current # potential GCD till it # is less than MAX while (j < = high) : # A multiple found if (count[j] > 0 ) : counter + = count[j] # Incrementing potential # GCD by itself # To check i, 2i, 3i.... j + = i # 2 multiples found, # max GCD found if (counter = = 2 ) : return i counter = 0 # Driver code # Array in which pair # with max GCD is to # be found arr = [ 1 , 2 , 4 , 8 , 8 , 12 ] # Size of array n = len (arr) print (findMaxGCD(arr, n)) #This code is contributed by Nikita Tiwari. |
C#
// C# Code to find pair with // maximum GCD in an array using System; class GFG { // function to find GCD // of pair with max // max GCD in the array public static int findMaxGCD( int []arr, int n) { // Calculating Max // in array int high = 0; for ( int i = 0; i < n; i++) high = Math.Max(high, arr[i]); // Maintaining count array int []count= new int [high + 1]; for ( int i = 0; i < n; i++) count[arr[i]]++; // Variable to store // the multiples of // a number int counter = 0; // Iterating from MAX // to 1 GCD is always // between MAX and 1 // The first GCD found // will be the highest // as we are decrementing // the potential GCD for ( int i = high; i >= 1; i--) { int j = i; // Iterating from current // potential GCD till it // is less than MAX while (j <= high) { // A multiple found if (count[j]>0) counter+=count[j]; // Incrementing potential // GCD by itself // To check i, 2i, 3i.... j += i; // 2 multiples found, // max GCD found if (counter == 2) return i; } counter=0; } return 1; } // Driver Code public static void Main(String []args) { // Array in which pair // with max GCD is to // be found int []arr = {1, 2, 4, 8, 8, 12}; // Size of array int n = arr.Length; Console.WriteLine(findMaxGCD(arr,n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Code to Find pair with maximum // GCD in an array // function to find GCD of pair with // max GCD in the array function findMaxGCD( $arr , $n ) { // Calculating MAX in array $high = 0; for ( $i = 0; $i < $n ; $i ++) $high = max( $high , $arr [ $i ]); // Maintaining count array $count = array_fill (0, $high + 1, 0); for ( $i = 0; $i < $n ; $i ++) $count [ $arr [ $i ]]++; // Variable to store the multiples // of a number $counter = 0; // Iterating from MAX to 1 GCD is always // between MAX and 1. The first GCD found // will be the highest as we are decrementing // the potential GCD for ( $i = $high ; $i >= 1; $i --) { $j = $i ; $counter = 0; // Iterating from current potential GCD // till it is less than MAX while ( $j <= $high ) { // A multiple found if ( $count [ $j ] >= 2) return $j ; else if ( $count [ $j ] == 1) $counter ++; // Incrementing potential GCD by itself // To check i, 2i, 3i.... $j += $i ; // 2 multiples found, max GCD found if ( $counter == 2) return $i ; } } } // Driver code // Array in which pair with max GCD // is to be found $arr = array ( 1, 2, 4, 8, 8, 12 ); // Size of array $n = count ( $arr ); print (findMaxGCD( $arr , $n )); // This code is contributed by mits ?> |
Javascript
<script> // javascript Code to // Find pair with // maximum GCD in // an array // function to find // GCD of pair with // max GCD in the // array function findMaxGCD(arr , n) { // Calculating MAX in // array var high = 0; for (let i = 0; i < n; i++) high = Math.max(high, arr[i]); // Maintaining count array var count = Array(high + 1).fill(0); for (let i = 0; i < n; i++) count[arr[i]]++; // Variable to store // the multiples of // a number var counter = 0; // Iterating from MAX // to 1 GCD is always // between MAX and 1 // The first GCD found // will be the highest // as we are decrementing // the potential GCD for (let i = high; i >= 1; i--) { var j = i; // Iterating from current // potential GCD till it // is less than MAX while (j <= high) { // A multiple found if (count[j] > 0) counter += count[j]; // Incrementing potential // GCD by itself // To check i, 2i, 3i.... j += i; // 2 multiples found, // max GCD found if (counter == 2) return i; } counter = 0; } return 1; } /* Driver program to test above function */ // Array in which pair // with max GCD is to // be found var arr = [ 1, 2, 4, 8, 8, 12 ]; // Size of array var n = arr.length; document.write(findMaxGCD(arr, n)); // This code is contributed by aashish1995 </script> |
输出：
8
时间复杂性 ：这种方法的时间复杂性一直是一个开放的问题，称为狄利克莱除数问题。 本文由 罗希特·塔普里亚尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
