Dada una array A[] que consta de N enteros positivos, la tarea es verificar si todos los elementos de la array son coprimos por pares , es decir, para todos los pares (A i , A j ), tal que 1<=i<j<= norte, MCD(UN yo , UN j ) = 1 .
Ejemplos:
Entrada: A[] = {2, 3, 5}
Salida: Sí
Explicación: Todos los pares, (2, 3), (3, 5), (2, 5) son pares coprimos.Entrada: A[] = {5, 10}
Salida: No
Explicación: GCD(5, 10)=5 por lo que no son coprimos.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles a partir de una array dada y, para cada par, verificar si es coprimo o no. Si se encuentra que algún par no es coprimo, escriba » No «. De lo contrario, escriba “ Sí ”.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de la siguiente observación:
Si dos números cualesquiera tienen un factor primo común , entonces su MCD nunca puede ser 1.
Esto también se puede interpretar como:
El MCM de la array debe ser igual al producto de los elementos de la array.
Por lo tanto, la solución se reduce a calcular el LCM de la array dada y verificar si es igual al producto de todos los elementos de la array o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to calculate GCD
ll GCD(ll a, ll b)
{
if (a == 0)
return b;
return GCD(b % a, a);
}
// Function to calculate LCM
ll LCM(ll a, ll b)
{
return (a * b)
/ GCD(a, b);
}
// Function to check if all elements
// in the array are pairwise coprime
void checkPairwiseCoPrime(int A[], int n)
{
// Initialize variables
ll prod = 1;
ll lcm = 1;
// Iterate over the array
for (int i = 0; i < n; i++) {
// Calculate product of
// array elements
prod *= A[i];
// Calculate LCM of
// array elements
lcm = LCM(A[i], lcm);
}
// If the product of array elements
// is equal to LCM of the array
if (prod == lcm)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Driver Code
int main()
{
int A[] = { 2, 3, 5 };
int n = sizeof(A) / sizeof(A[0]);
// Function call
checkPairwiseCoPrime(A, n);
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to calculate GCD
static long GCD(long a, long b)
{
if (a == 0)
return b;
return GCD(b % a, a);
}
// Function to calculate LCM
static long LCM(long a, long b)
{
return (a * b) / GCD(a, b);
}
// Function to check if all elements
// in the array are pairwise coprime
static void checkPairwiseCoPrime(int A[], int n)
{
// Initialize variables
long prod = 1;
long lcm = 1;
// Iterate over the array
for(int i = 0; i < n; i++)
{
// Calculate product of
// array elements
prod *= A[i];
// Calculate LCM of
// array elements
lcm = LCM(A[i], lcm);
}
// If the product of array elements
// is equal to LCM of the array
if (prod == lcm)
System.out.println("Yes");
else
System.out.println("No");
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 2, 3, 5 };
int n = A.length;
// Function call
checkPairwiseCoPrime(A, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to calculate GCD
def GCD(a, b):
if (a == 0):
return b
return GCD(b % a, a)
# Function to calculate LCM
def LCM(a, b):
return (a * b) // GCD(a, b)
# Function to check if aelements
# in the array are pairwise coprime
def checkPairwiseCoPrime(A, n):
# Initialize variables
prod = 1
lcm = 1
# Iterate over the array
for i in range(n):
# Calculate product of
# array elements
prod *= A[i]
# Calculate LCM of
# array elements
lcm = LCM(A[i], lcm)
# If the product of array elements
# is equal to LCM of the array
if (prod == lcm):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
A = [ 2, 3, 5 ]
n = len(A)
# Function call
checkPairwiseCoPrime(A, n)
# This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate GCD
static long GCD(long a,
long b)
{
if (a == 0)
return b;
return GCD(b % a, a);
}
// Function to calculate LCM
static long LCM(long a,
long b)
{
return (a * b) / GCD(a, b);
}
// Function to check if all elements
// in the array are pairwise coprime
static void checkPairwiseCoPrime(int []A,
int n)
{
// Initialize variables
long prod = 1;
long lcm = 1;
// Iterate over the array
for(int i = 0; i < n; i++)
{
// Calculate product of
// array elements
prod *= A[i];
// Calculate LCM of
// array elements
lcm = LCM(A[i], lcm);
}
// If the product of array elements
// is equal to LCM of the array
if (prod == lcm)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
// Driver Code
public static void Main(String[] args)
{
int []A = {2, 3, 5};
int n = A.Length;
// Function call
checkPairwiseCoPrime(A, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program for the above approach
// Function to calculate GCD
function GCD(a , b) {
if (a == 0)
return b;
return GCD(b % a, a);
}
// Function to calculate LCM
function LCM(a , b) {
return (a * b) / GCD(a, b);
}
// Function to check if all elements
// in the array are pairwise coprime
function checkPairwiseCoPrime(A , n) {
// Initialize variables
var prod = 1;
var lcm = 1;
// Iterate over the array
for (i = 0; i < n; i++) {
// Calculate product of
// array elements
prod *= A[i];
// Calculate LCM of
// array elements
lcm = LCM(A[i], lcm);
}
// If the product of array elements
// is equal to LCM of the array
if (prod == lcm)
document.write("Yes");
else
document.write("No");
}
// Driver Code
var A = [ 2, 3, 5 ];
var n = A.length;
// Function call
checkPairwiseCoPrime(A, n);
// This code contributed by umadevi9616
</script>
Yes
Complejidad de tiempo: O(N log (min(A[i])))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Srishtik Dutta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA