Dada una array arr[] de N enteros. La tarea es encontrar todos los divisores comunes de todos los N enteros.
Ejemplos
Entrada: arr[] = {6, 90, 12, 18, 30, 18}
Salida: 1 2 3 6
Explicación:
MCD de todos los números es 6.
Ahora para encontrar todos los divisores de 6, tenemos
6 = 1 * 6
6 = 2 * 3
Por lo tanto, 1, 2, 3 y 6 son los divisores comunes de {6, 90, 12, 18, 20, 18}.
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 1
Explicación:
el MCD de todos los números es 1.
Por lo tanto, solo hay un divisor común de todos los números, es decir, 1.
Acercarse:
- Para encontrar los divisores comunes de todos los N enteros en la array dada arr[], encuentre los máximos divisores comunes (mcd) de todos los enteros en arr[] .
- Encuentre todos los divisores de los máximos comunes divisores (mcd) obtenidos en el paso anterior usando el enfoque discutido en este artículo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find all common
// divisors of N numbers
#include <bits/stdc++.h>
using namespace std;
// Function to calculate gcd of
// two numbers
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to print all the
// common divisors
void printAllDivisors(int arr[], int N)
{
// Variable to find the gcd
// of N numbers
int g = arr[0];
// Set to store all the
// common divisors
set<int> divisors;
// Finding GCD of the given
// N numbers
for (int i = 1; i < N; i++) {
g = gcd(arr[i], g);
}
// Finding divisors of the
// HCF of n numbers
for (int i = 1; i * i <= g; i++) {
if (g % i == 0) {
divisors.insert(i);
if (g / i != i)
divisors.insert(g / i);
}
}
// Print all the divisors
for (auto& it : divisors)
cout << it << " ";
}
// Driver's Code
int main()
{
int arr[] = { 6, 90, 12, 18, 30, 24 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function to print all the
// common divisors
printAllDivisors(arr, n);
return 0;
}
Java
// Java program to find all common
// divisors of N numbers
import java.util.*;
class GFG
{
// Function to calculate gcd of
// two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to print all the
// common divisors
static void printAllDivisors(int arr[], int N)
{
// Variable to find the gcd
// of N numbers
int g = arr[0];
// Set to store all the
// common divisors
HashSet<Integer> divisors = new HashSet<Integer>();
// Finding GCD of the given
// N numbers
for (int i = 1; i < N; i++)
{
g = gcd(arr[i], g);
}
// Finding divisors of the
// HCF of n numbers
for (int i = 1; i * i <= g; i++)
{
if (g % i == 0)
{
divisors.add(i);
if (g / i != i)
divisors.add(g / i);
}
}
// Print all the divisors
for (int it : divisors)
System.out.print(it+ " ");
}
// Driver's Code
public static void main(String[] args)
{
int arr[] = { 6, 90, 12, 18, 30, 24 };
int n = arr.length;
// Function to print all the
// common divisors
printAllDivisors(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find all common # divisors of N numbers # Function to calculate gcd of # two numbers def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Function to print all the # common divisors def printAllDivisors(arr, N): # Variable to find the gcd # of N numbers g = arr[0] # Set to store all the # common divisors divisors = dict() # Finding GCD of the given # N numbers for i in range(1, N): g = gcd(arr[i], g) # Finding divisors of the # HCF of n numbers for i in range(1, g + 1): if i*i > g: break if (g % i == 0): divisors[i] = 1 if (g // i != i): divisors[g // i] = 1 # Print all the divisors for it in sorted(divisors): print(it, end=" ") # Driver's Code if __name__ == '__main__': arr= [6, 90, 12, 18, 30, 24] n = len(arr) # Function to print all the # common divisors printAllDivisors(arr, n) # This code is contributed by mohit kumar 29
C#
// C# program to find all common
// divisors of N numbers
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate gcd of
// two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to print all the
// common divisors
static void printAllDivisors(int []arr, int N)
{
// Variable to find the gcd
// of N numbers
int g = arr[0];
// Set to store all the
// common divisors
HashSet<int> divisors = new HashSet<int>();
// Finding GCD of the given
// N numbers
for (int i = 1; i < N; i++)
{
g = gcd(arr[i], g);
}
// Finding divisors of the
// HCF of n numbers
for (int i = 1; i * i <= g; i++)
{
if (g % i == 0)
{
divisors.Add(i);
if (g / i != i)
divisors.Add(g / i);
}
}
// Print all the divisors
foreach (int it in divisors)
Console.Write(it+ " ");
}
// Driver's Code
public static void Main(String[] args)
{
int []arr = { 6, 90, 12, 18, 30, 24 };
int n = arr.Length;
// Function to print all the
// common divisors
printAllDivisors(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find all common
// divisors of N numbers
// Function to calculate gcd of
// two numbers
function gcd(a,b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to print all the
// common divisors
function printAllDivisors(arr, N)
{
// Variable to find the gcd
// of N numbers
let g = arr[0];
// Set to store all the
// common divisors
let divisors = new Set();
// Finding GCD of the given
// N numbers
for (let i = 1; i < N; i++)
{
g = gcd(arr[i], g);
}
// Finding divisors of the
// HCF of n numbers
for (let i = 1; i * i <= g; i++)
{
if (g % i == 0)
{
divisors.add(i);
if (Math.floor(g / i) != i)
divisors.add(Math.floor(g / i));
}
}
// Print all the divisors
for (let it of divisors.values())
document.write(it+ " ");
}
// Driver's Code
let arr=[6, 90, 12, 18, 30, 24];
let n = arr.length;
// Function to print all the
// common divisors
printAllDivisors(arr, n);
// This code is contributed by unknown2108
</script>
Producción:
1 2 3 6
Complejidad de tiempo: O(N*log(M)) donde N es la longitud de la array dada y M es el elemento máximo en la array.
Espacio auxiliar: O((log(max(a, b))) 3/2 )
Publicación traducida automáticamente
Artículo escrito por isocyanide7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA