共素数对或互素数对是指GCD为1的数对。给定一个大小为n的数组，找出数组中共素数或互素数对的数目。
null
例如：
Input : 1 2 3Output : 3Here, Co-prime pairs are ( 1, 2), ( 2, 3), ( 1, 3) Input :4 8 3 9Output :4Here, Co-prime pairs are ( 4, 3), ( 8, 3), ( 4, 9 ), ( 8, 9 )
方法： 使用两个循环，检查阵列的每一对。如果配对的Gcd为1，则递增计数器值，最后显示它。
C++
// C++ program to find // number of co-prime // pairs in array #include <bits/stdc++.h> using namespace std; // function to check for gcd bool coprime( int a, int b) { return (__gcd(a, b) == 1); } // Recursive function to // return gcd of a and b int numOfPairs( int arr[], int n) { int count = 0; for ( int i = 0; i < n - 1; i++) for ( int j = i + 1; j < n; j++) if (coprime(arr[i], arr[j])) count++; return count; } // driver code int main() { int arr[] = { 1, 2, 5, 4, 8, 3, 9 }; int n = sizeof (arr) / sizeof (arr[0]); cout << numOfPairs(arr, n); return 0; } |
JAVA
// Java program to find // number of co-prime // pairs in array import java.io.*; 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 ; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } // function to check for gcd static boolean coprime( int a, int b) { return (gcd(a, b) == 1 ); } // Returns count of co-prime // pairs present in array static int numOfPairs( int arr[], int n) { int count = 0 ; for ( int i = 0 ; i < n - 1 ; i++) for ( int j = i + 1 ; j < n; j++) if (coprime(arr[i], arr[j])) count++; return count; } // driver code public static void main(String args[]) throws IOException { int arr[] = { 1 , 2 , 5 , 4 , 8 , 3 , 9 }; int n = arr.length; System.out.println(numOfPairs(arr, n)); } } /* This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 program to # find number of co # prime pairs in array # Recursive function to # return gcd of a and b def gcd(a, b): # Everything divides 0 if (a = = 0 or b = = 0 ): return False # base case if (a = = b): return a # a is greater if (a > b): return gcd(a - b, b) return gcd(a, b - a) # function to check # for gcd def coprime(a, b) : return (gcd(a, b) = = 1 ) # Returns count of # co-prime pairs # present in array def numOfPairs(arr, n) : count = 0 for i in range ( 0 , n - 1 ) : for j in range (i + 1 , n) : if (coprime(arr[i], arr[j])) : count = count + 1 return count # driver code arr = [ 1 , 2 , 5 , 4 , 8 , 3 , 9 ] n = len (arr) print (numOfPairs(arr, n)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find number of // co-prime pairs in array 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; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } // function to check for gcd static bool coprime( int a, int b) { return (gcd(a, b) == 1); } // Returns count of co-prime // pairs present in array static int numOfPairs( int []arr, int n) { int count = 0; for ( int i = 0; i < n - 1; i++) for ( int j = i + 1; j < n; j++) if (coprime(arr[i], arr[j])) count++; return count; } // driver code public static void Main() { int []arr = { 1, 2, 5, 4, 8, 3, 9 }; int n = arr.Length; Console.WriteLine(numOfPairs(arr, n)); } } //This code is contributed by Anant Agarwal. |
PHP
<?php // PHP program to find // number of co-prime // pairs in array // Recursive function to // return gcd of a and b function __gcd( $a , $b ) { // Everything divides 0 if ( $a == 0 or $b == 0) return 0; // base case if ( $a == $b ) return $a ; // a is greater if ( $a > $b ) return __gcd( $a - $b , $b ); return __gcd( $a , $b - $a ); } // function to check for gcd function coprime( $a , $b ) { return (__gcd( $a , $b ) == 1); } // Recursive function to // return gcd of a and b function numOfPairs( $arr , $n ) { $count = 0; for ( $i = 0; $i < $n - 1; $i ++) for ( $j = $i + 1; $j < $n ; $j ++) if (coprime( $arr [ $i ], $arr [ $j ])) $count ++; return $count ; } // Driver code $arr = array (1, 2, 5, 4, 8, 3, 9); $n = count ( $arr ); echo numOfPairs( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find // number of co-prime // pairs in array // Recursive function to // return gcd of a and b function gcd(a, b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Function to check for gcd function coprime(a, b) { return (gcd(a, b) == 1); } // Returns count of co-prime // pairs present in array function numOfPairs(arr, n) { let count = 0; for (let i = 0; i < n - 1; i++) for (let j = i + 1; j < n; j++) if (coprime(arr[i], arr[j])) count++; return count; } // Driver code let arr = [ 1, 2, 5, 4, 8, 3, 9 ]; let n = arr.length; document.write(numOfPairs(arr, n)); // This code is contributed by susmitakundugoaldanga </script> |
输出：
17
本文由 迪比恩杜·罗伊·乔杜里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
