Los pares coprimos o primos mutuos son aquellos pares de números cuyo MCD es 1. Dada una array de tamaño n, encuentre el número de pares coprimos o primos mutuos en la array.
Ejemplos:
Input : 1 2 3
Output : 3
Here, Co-prime pairs are ( 1, 2), ( 2, 3),
( 1, 3)
Input :4 8 3 9
Output :4
Here, Co-prime pairs are ( 4, 3), ( 8, 3),
( 4, 9 ), ( 8, 9 )
Enfoque: usando dos bucles, verifique todos los pares posibles de la array. Si Gcd del par es 1 valor de contador de incremento y al final mostrarlo.
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>
Producción:
17
Complejidad de tiempo: O (n 2 logn)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Dibyendu Roy Chaudhuri . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA