Dada una array arr[] , la tarea es verificar si todos los pares de una array son coprimos entre sí. Todos los pares de una array son coprimos cuando GCD(arr[i], arr[j]) = 1 se cumple para cada par (i, j) , tal que 1≤ i < j ≤ N .
Ejemplos:
Entrada: arr[] = {1, 3, 8}
Salida: Sí
Explicación:
Aquí, GCD(arr[0], arr[1]) = GCD(arr[0], arr[2]) = GCD(arr[ 1], arr[2]) = 1
Por lo tanto, todos los pares son coprimos entre sí.Entrada: arr[] = {6, 67, 24, 1}
Salida: No
Enfoque ingenuo: una solución simple es iterar sobre cada par (A[i], A[j]) de la array dada y verificar si el gcd (A[i], A[j]) = 1 o no. Por lo tanto, el único entero positivo (factor) que los divide a ambos es 1.
A continuación se muestra la implementación del enfoque ingenuo:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if all the
// pairs of the array are coprime
// with each other or not
bool allCoprime(int A[], int n)
{
bool all_coprime = true;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Check if GCD of the
// pair is not equal to 1
if (__gcd(A[i], A[j]) != 1) {
// All pairs are non-coprime
// Return false
all_coprime = false;
break;
}
}
}
return all_coprime;
}
// Driver Code
int main()
{
int A[] = { 3, 5, 11, 7, 19 };
int arr_size = sizeof(A) / sizeof(A[0]);
if (allCoprime(A, arr_size)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to check if all the
// pairs of the array are coprime
// with each other or not
static boolean allCoprime(int A[], int n)
{
boolean all_coprime = true;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Check if GCD of the
// pair is not equal to 1
if (gcd(A[i], A[j]) != 1)
{
// All pairs are non-coprime
// Return false
all_coprime = false;
break;
}
}
}
return all_coprime;
}
// Function return gcd of two number
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 3, 5, 11, 7, 19 };
int arr_size = A.length;
if (allCoprime(A, arr_size))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation of the
# above approach
def gcd(a, b):
if (b == 0):
return a
else:
return gcd(b, a % b)
# Function to check if all the
# pairs of the array are coprime
# with each other or not
def allCoprime(A, n):
all_coprime = True
for i in range(n):
for j in range(i + 1, n):
# Check if GCD of the
# pair is not equal to 1
if gcd(A[i], A[j]) != 1:
# All pairs are non-coprime
# Return false
all_coprime = False;
break
return all_coprime
# Driver code
if __name__=="__main__":
A = [ 3, 5, 11, 7, 19 ]
arr_size = len(A)
if (allCoprime(A, arr_size)):
print('Yes')
else:
print('No')
# This code is contributed by rutvik_56
C#
// C# implementation of the
// above approach
using System;
class GFG{
// Function to check if all the
// pairs of the array are coprime
// with each other or not
static bool allCoprime(int []A,
int n)
{
bool all_coprime = true;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Check if GCD of the
// pair is not equal to 1
if (gcd(A[i], A[j]) != 1)
{
// All pairs are non-coprime
// Return false
all_coprime = false;
break;
}
}
}
return all_coprime;
}
// Function return gcd of two number
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Driver Code
public static void Main(String[] args)
{
int []A = {3, 5, 11, 7, 19};
int arr_size = A.Length;
if (allCoprime(A, arr_size))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the
// above approach
function gcd(a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
}
// Function to check if all the
// pairs of the array are coprime
// with each other or not
function allCoprime( A, n)
{
var all_coprime = true;
for (var i = 0; i < n; i++) {
for (var j = i + 1; j < n; j++) {
// Check if GCD of the
// pair is not equal to 1
if (gcd(A[i], A[j]) != 1) {
// All pairs are non-coprime
// Return false
all_coprime = false;
break;
}
}
}
return all_coprime;
}
/* Driver Program */
var A = [ 3, 5, 11, 7, 19 ];
var arr_size = A.length;
if (allCoprime(A, arr_size)) {
console.log("Yes");
}
else {
console.log( "No");
}
// This code is contributed by ukasp.
</script>
Producción:
Yes
Complejidad temporal: O(N 2 logN)
Espacio auxiliar: O(1)
Enfoque eficiente: la observación clave en el problema es que se dice que dos números son coprimos si solo el entero positivo (factor) que los divide a ambos es 1. Entonces, podemos almacenar los factores de cada elemento de la array en el contenedor (conjunto, array, etc.) que incluye este elemento, y verifique si este factor ya está presente o no.
Ilustración:
Para el arreglo arr[] = {6, 5, 10, 3}
Dado que los pares (6, 10), (6, 3) y (5, 10) tienen factores comunes, todos los pares del arreglo no son primos entre sí. otro.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to store and
// check the factors
bool findFactor(int value,
unordered_set<int>& factors)
{
factors.insert(value);
for (int i = 2; i * i <= value; i++) {
if (value % i == 0) {
// Check if factors are equal
if (value / i == i) {
// Check if the factor is
// already present
if (factors.find(i)
!= factors.end()) {
return true;
}
else {
// Insert the factor in set
factors.insert(i);
}
}
else {
// Check if the factor is
// already present
if (factors.find(i) != factors.end()
|| factors.find(value / i)
!= factors.end()) {
return true;
}
else {
// Insert the factors in set
factors.insert(i);
factors.insert(value / i);
}
}
}
}
return false;
}
// Function to check if all the
// pairs of array elements
// are coprime with each other
bool allCoprime(int A[], int n)
{
bool all_coprime = true;
unordered_set<int> factors;
for (int i = 0; i < n; i++) {
if (A[i] == 1)
continue;
// Check if factors of A[i]
// haven't occurred previously
if (findFactor(A[i], factors)) {
all_coprime = false;
break;
}
}
return all_coprime;
}
// Driver Code
int main()
{
int A[] = { 3, 5, 11, 7, 19 };
int arr_size = sizeof(A) / sizeof(A[0]);
if (allCoprime(A, arr_size)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG{
// Function to store and
// check the factors
static boolean findFactor(int value,
HashSet<Integer> factors)
{
factors.add(value);
for (int i = 2; i * i <= value; i++)
{
if (value % i == 0)
{
// Check if factors are equal
if (value / i == i)
{
// Check if the factor is
// already present
if (factors.contains(i))
{
return true;
}
else
{
// Insert the factor in set
factors.add(i);
}
}
else
{
// Check if the factor is
// already present
if (factors.contains(i) ||
factors.contains(value / i))
{
return true;
}
else
{
// Insert the factors in set
factors.add(i);
factors.add(value / i);
}
}
}
}
return false;
}
// Function to check if all the
// pairs of array elements
// are coprime with each other
static boolean allCoprime(int A[], int n)
{
boolean all_coprime = true;
HashSet<Integer> factors =
new HashSet<Integer>();
for (int i = 0; i < n; i++)
{
if (A[i] == 1)
continue;
// Check if factors of A[i]
// haven't occurred previously
if (findFactor(A[i], factors))
{
all_coprime = false;
break;
}
}
return all_coprime;
}
// Driver Code
public static void main(String[] args)
{
int A[] = {3, 5, 11, 7, 19};
int arr_size = A.length;
if (allCoprime(A, arr_size))
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 implementation of
# the above approach
# Function to store and
# check the factors
def findFactor(value, factors):
factors.add(value)
i = 2
while(i * i <= value):
if value % i == 0:
# Check if factors are equal
if value // i == i:
# Check if the factor is
# already present
if i in factors:
return bool(True)
else:
# Insert the factor in set
factors.add(i)
else:
# Check if the factor is
# already present
if (i in factors) or
((value // i) in factors):
return bool(True)
else :
# Insert the factors in set
factors.add(i)
factors.add(value // i)
i += 1
return bool(False)
# Function to check if all the
# pairs of array elements
# are coprime with each other
def allCoprime(A, n):
all_coprime = bool(True)
factors = set()
for i in range(n):
if A[i] == 1:
continue
# Check if factors of A[i]
# haven't occurred previously
if findFactor(A[i], factors):
all_coprime = bool(False)
break
return bool(all_coprime)
# Driver code
A = [3, 5, 11, 7, 19]
arr_size = len(A)
if (allCoprime(A, arr_size)):
print("Yes")
else:
print("No")
# This code is contributed by divyeshrabadiya07
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to store and
// check the factors
static bool findFactor(int value,
HashSet<int> factors)
{
factors.Add(value);
for(int i = 2; i * i <= value; i++)
{
if (value % i == 0)
{
// Check if factors are equal
if (value / i == i)
{
// Check if the factor is
// already present
if (factors.Contains(i))
{
return true;
}
else
{
// Insert the factor in set
factors.Add(i);
}
}
else
{
// Check if the factor is
// already present
if (factors.Contains(i) ||
factors.Contains(value / i))
{
return true;
}
else
{
// Insert the factors in set
factors.Add(i);
factors.Add(value / i);
}
}
}
}
return false;
}
// Function to check if all the
// pairs of array elements
// are coprime with each other
static bool allCoprime(int []A, int n)
{
bool all_coprime = true;
HashSet<int> factors = new HashSet<int>();
for(int i = 0; i < n; i++)
{
if (A[i] == 1)
continue;
// Check if factors of A[i]
// haven't occurred previously
if (findFactor(A[i], factors))
{
all_coprime = false;
break;
}
}
return all_coprime;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 3, 5, 11, 7, 19 };
int arr_size = A.Length;
if (allCoprime(A, arr_size))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed by Amit Katiyar
Producción:
Yes
Complejidad temporal: O(N 3/2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por se_prashant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA