Dados dos números enteros, la tarea es encontrar el conteo de todos los divisores comunes de números dados.
Ejemplos:
Input : a = 12, b = 24 Output: 6 // all common divisors are 1, 2, 3, // 4, 6 and 12 Input : a = 3, b = 17 Output: 1 // all common divisors are 1 Input : a = 20, b = 36 Output: 3 // all common divisors are 1, 2, 4
Se recomienda hacer referencia a todos los divisores de un número dado como requisito previo de este artículo.
Solución ingenua
Una solución simple es primero encontrar todos los divisores del primer número y almacenarlos en una array o hash. Luego encuentra los divisores comunes del segundo número y guárdalos. Finalmente imprima elementos comunes de dos arrays almacenadas o hash. La clave es que la magnitud de las potencias de los factores primos de un divisor debe ser igual a la potencia mínima de dos factores primos de a y b.
- Encuentre los factores primos de a usando la descomposición en factores primos .
- Encuentre el recuento de cada factor primo de a y guárdelo en un Hashmap.
- Prime factorice b usando distintos factores primos de a .
- Entonces el número total de divisores sería igual al producto de (cuenta + 1)
de cada factor. - cuenta es el mínimo de cuentas de cada factor primo de a y b.
- Esto da la cuenta de todos los divisores de a y b .
C++
// C++ implementation of program
#include <bits/stdc++.h>
using namespace std;
// Map to store the count of each
// prime factor of a
map<int, int> ma;
// Function that calculate the count of
// each prime factor of a number
void primeFactorize(int a)
{
for(int i = 2; i * i <= a; i += 2)
{
int cnt = 0;
while (a % i == 0)
{
cnt++;
a /= i;
}
ma[i] = cnt;
}
if (a > 1)
{
ma[a] = 1;
}
}
// Function to calculate all common
// divisors of two given numbers
// a, b --> input integer numbers
int commDiv(int a, int b)
{
// Find count of each prime factor of a
primeFactorize(a);
// stores number of common divisors
int res = 1;
// Find the count of prime factors
// of b using distinct prime factors of a
for(auto m = ma.begin();
m != ma.end(); m++)
{
int cnt = 0;
int key = m->first;
int value = m->second;
while (b % key == 0)
{
b /= key;
cnt++;
}
// Prime factor of common divisor
// has minimum cnt of both a and b
res *= (min(cnt, value) + 1);
}
return res;
}
// Driver code
int main()
{
int a = 12, b = 24;
cout << commDiv(a, b) << endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java implementation of program
import java.util.*;
import java.io.*;
class GFG {
// map to store the count of each prime factor of a
static HashMap<Integer, Integer> ma = new HashMap<>();
// method that calculate the count of
// each prime factor of a number
static void primeFactorize(int a)
{
for (int i = 2; i * i <= a; i += 2) {
int cnt = 0;
while (a % i == 0) {
cnt++;
a /= i;
}
ma.put(i, cnt);
}
if (a > 1)
ma.put(a, 1);
}
// method to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
static int commDiv(int a, int b)
{
// Find count of each prime factor of a
primeFactorize(a);
// stores number of common divisors
int res = 1;
// Find the count of prime factors of b using
// distinct prime factors of a
for (Map.Entry<Integer, Integer> m : ma.entrySet()) {
int cnt = 0;
int key = m.getKey();
int value = m.getValue();
while (b % key == 0) {
b /= key;
cnt++;
}
// prime factor of common divisor
// has minimum cnt of both a and b
res *= (Math.min(cnt, value) + 1);
}
return res;
}
// Driver method
public static void main(String args[])
{
int a = 12, b = 24;
System.out.println(commDiv(a, b));
}
}
Python3
# Python3 implementation of program
import math
# Map to store the count of each
# prime factor of a
ma = {}
# Function that calculate the count of
# each prime factor of a number
def primeFactorize(a):
sqt = int(math.sqrt(a))
for i in range(2, sqt, 2):
cnt = 0
while (a % i == 0):
cnt += 1
a /= i
ma[i] = cnt
if (a > 1):
ma[a] = 1
# Function to calculate all common
# divisors of two given numbers
# a, b --> input integer numbers
def commDiv(a, b):
# Find count of each prime factor of a
primeFactorize(a)
# stores number of common divisors
res = 1
# Find the count of prime factors
# of b using distinct prime factors of a
for key, value in ma.items():
cnt = 0
while (b % key == 0):
b /= key
cnt += 1
# Prime factor of common divisor
# has minimum cnt of both a and b
res *= (min(cnt, value) + 1)
return res
# Driver code
a = 12
b = 24
print(commDiv(a, b))
# This code is contributed by Stream_Cipher
C#
// C# implementation of program
using System;
using System.Collections.Generic;
class GFG{
// Map to store the count of each
// prime factor of a
static Dictionary<int,
int> ma = new Dictionary<int,
int>();
// Function that calculate the count of
// each prime factor of a number
static void primeFactorize(int a)
{
for(int i = 2; i * i <= a; i += 2)
{
int cnt = 0;
while (a % i == 0)
{
cnt++;
a /= i;
}
ma.Add(i, cnt);
}
if (a > 1)
ma.Add(a, 1);
}
// Function to calculate all common
// divisors of two given numbers
// a, b --> input integer numbers
static int commDiv(int a, int b)
{
// Find count of each prime factor of a
primeFactorize(a);
// Stores number of common divisors
int res = 1;
// Find the count of prime factors
// of b using distinct prime factors of a
foreach(KeyValuePair<int, int> m in ma)
{
int cnt = 0;
int key = m.Key;
int value = m.Value;
while (b % key == 0)
{
b /= key;
cnt++;
}
// Prime factor of common divisor
// has minimum cnt of both a and b
res *= (Math.Min(cnt, value) + 1);
}
return res;
}
// Driver code
static void Main()
{
int a = 12, b = 24;
Console.WriteLine(commDiv(a, b));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript implementation of program
// Map to store the count of each
// prime factor of a
let ma = new Map();
// Function that calculate the count of
// each prime factor of a number
function primeFactorize(a)
{
for(let i = 2; i * i <= a; i += 2)
{
let cnt = 0;
while (a % i == 0)
{
cnt++;
a = parseInt(a / i, 10);
}
ma.set(i, cnt);
}
if (a > 1)
{
ma.set(a, 1);
}
}
// Function to calculate all common
// divisors of two given numbers
// a, b --> input integer numbers
function commDiv(a,b)
{
// Find count of each prime factor of a
primeFactorize(a);
// stores number of common divisors
let res = 1;
// Find the count of prime factors
// of b using distinct prime factors of a
ma.forEach((values,keys)=>{
let cnt = 0;
let key = keys;
let value = values;
while (b % key == 0)
{
b = parseInt(b / key, 10);
cnt++;
}
// Prime factor of common divisor
// has minimum cnt of both a and b
res *= (Math.min(cnt, value) + 1);
})
return res;
}
// Driver code
let a = 12, b = 24;
document.write(commDiv(a, b));
</script>
Producción:
6
Complejidad temporal : O(√n log n)
Espacio auxiliar: O(n)
Solución eficiente:
una mejor solución es calcular el máximo común divisor (mcd) de dos números dados y luego contar los divisores de ese mcd.
C++
// C++ implementation of program
#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 calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
int commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
// Count divisors of n.
int result = 0;
for (int i = 1; i <= sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
// Driver program to run the case
int main()
{
int a = 12, b = 24;
cout << commDiv(a, b);
return 0;
}
Java
// Java implementation of program
class Test {
// method to calculate gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// method to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
static int commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
// Count divisors of n.
int result = 0;
for (int i = 1; i <= Math.sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
// Driver method
public static void main(String args[])
{
int a = 12, b = 24;
System.out.println(commDiv(a, b));
}
}
Python3
# Python implementation of program from math import sqrt # Function to calculate gcd of two numbers def gcd(a, b): if a == 0: return b return gcd(b % a, a) # Function to calculate all common divisors # of two given numbers # a, b --> input integer numbers def commDiv(a, b): # find GCD of a, b n = gcd(a, b) # Count divisors of n result = 0 for i in range(1,int(sqrt(n))+1): # if i is a factor of n if n % i == 0: # check if divisors are equal if n/i == i: result += 1 else: result += 2 return result # Driver program to run the case if __name__ == "__main__": a = 12 b = 24; print(commDiv(a, b))
C#
// C# implementation of program
using System;
class GFG {
// method to calculate gcd
// of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// method to calculate all
// common divisors of two
// given numbers a, b -->
// input integer numbers
static int commDiv(int a, int b)
{
// find gcd of a, b
int n = gcd(a, b);
// Count divisors of n.
int result = 0;
for (int i = 1; i <= Math.Sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
// Driver method
public static void Main(String[] args)
{
int a = 12, b = 24;
Console.Write(commDiv(a, b));
}
}
// This code contributed by parashar.
PHP
<?php
// PHP implementation of program
// Function to calculate
// gcd of two numbers
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Function to calculate all common
// divisors of two given numbers
// a, b --> input integer numbers
function commDiv($a, $b)
{
// find gcd of a, b
$n = gcd($a, $b);
// Count divisors of n.
$result = 0;
for ($i = 1; $i <= sqrt($n);
$i++)
{
// if 'i' is factor of n
if ($n % $i == 0)
{
// check if divisors
// are equal
if ($n / $i == $i)
$result += 1;
else
$result += 2;
}
}
return $result;
}
// Driver Code
$a = 12; $b = 24;
echo(commDiv($a, $b));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript implementation of program
// Function to calculate gcd of two numbers
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to calculate all common divisors
// of two given numbers
// a, b --> input integer numbers
function commDiv(a, b)
{
// find gcd of a, b
let n = gcd(a, b);
// Count divisors of n.
let result = 0;
for (let i = 1; i <= Math.sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i)
result += 1;
else
result += 2;
}
}
return result;
}
let a = 12, b = 24;
document.write(commDiv(a, b));
</script>
Producción :
6
Complejidad temporal: O(n 1/2 ) donde n es el mcd de dos números.
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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