Recuento máximo de divisores comunes de A y B de modo que todos sean coprimos entre sí

Dados dos enteros A y B . La tarea es encontrar el número máximo de elementos de los divisores comunes de A y B de modo que todos los elementos seleccionados sean coprimos entre sí.
Ejemplos: 
 

Entrada: A = 12, B = 18 
Salida: 3 
Los divisores comunes de A y B son 1, 2, 3 y 6. 
Seleccione 1, 2 y 3. Todos los pares son coprimos 
entre sí, es decir mcd(1, 2 ) = mcd(1, 3) = mcd(2, 3) = 1.
Entrada: A = 1, B = 3 
Salida: 1 
 

Planteamiento: Se puede observar que todos los factores comunes de A y B deben ser factor de su mcd . Y, para que los factores de este mcd sean coprimos entre sí, un elemento del par debe ser 1 o ambos elementos deben ser primos . Entonces la respuesta será 1 más que el conteo de divisores primos de mcd(A, B) . Tenga en cuenta que se suma 1 porque 1 también puede ser parte de los divisores elegidos ya que su mcd con los otros pares siempre será 1 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of common factors
// of a and b such that all the elements
// are co-prime to one another
int maxCommonFactors(int a, int b)
{
    // GCD of a and b
    int gcd = __gcd(a, b);
 
    // Include 1 initially
    int ans = 1;
 
    // Find all the prime factors of the gcd
    for (int i = 2; i * i <= gcd; i++) {
        if (gcd % i == 0) {
            ans++;
            while (gcd % i == 0)
                gcd /= i;
        }
    }
 
    // If gcd is prime
    if (gcd != 1)
        ans++;
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int a = 12, b = 18;
 
    cout << maxCommonFactors(a, b);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
// Function to return the count of common factors
// of a and b such that all the elements
// are co-prime to one another
static int maxCommonFactors(int a, int b)
{
     
    // GCD of a and b
    int __gcd = gcd(a, b);
 
    // Include 1 initially
    int ans = 1;
 
    // Find all the prime factors of the gcd
    for (int i = 2; i * i <= __gcd; i++)
    {
        if (__gcd % i == 0)
        {
            ans++;
            while (__gcd % i == 0)
                __gcd /= i;
        }
    }
 
    // If gcd is prime
    if (__gcd != 1)
        ans++;
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
    int a = 12, b = 18;
 
    System.out.println(maxCommonFactors(a, b));
}
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
import math
 
# Function to return the count of common factors
# of a and b such that all the elements
# are co-prime to one another
def maxCommonFactors(a, b):
     
    # GCD of a and b
    gcd = math.gcd(a, b)
 
    # Include 1 initially
    ans = 1;
 
    # Find all the prime factors of the gcd
    i = 2
    while (i * i <= gcd):
        if (gcd % i == 0):
            ans += 1
            while (gcd % i == 0):
                gcd = gcd // i
        i += 1   
                 
    # If gcd is prime
    if (gcd != 1):
        ans += 1
 
    # Return the required answer
    return ans
     
# Driver code
a = 12
b = 18
print(maxCommonFactors(a, b))
 
# This code is contributed by
# divyamohan123

// C# implementation of the above approach
using System;        
 
class GFG
{
     
    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Function to return the count of common factors
    // of a and b such that all the elements
    // are co-prime to one another
    static int maxCommonFactors(int a, int b)
    {
 
        // GCD of a and b
        int __gcd = gcd(a, b);
 
        // Include 1 initially
        int ans = 1;
 
        // Find all the prime factors of the gcd
        for (int i = 2; i * i <= __gcd; i++)
        {
            if (__gcd % i == 0)
            {
                ans++;
                while (__gcd % i == 0)
                    __gcd /= i;
            }
        }
 
        // If gcd is prime
        if (__gcd != 1)
            ans++;
 
        // Return the required answer
        return ans;
    }
 
    // Driver code
    public static void Main (String[] args)
    {
        int a = 12, b = 18;
 
        Console.WriteLine(maxCommonFactors(a, b));
    }
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript implementation of the approach
 
function GCD(a, b)
{
  if (b == 0)
      return a;
  return GCD(b, a % b);
}
     
// Function to return the count of common factors
// of a and b such that all the elements
// are co-prime to one another
function maxCommonFactors(a, b)
{
    // GCD of a and b
    let gcd = GCD(a, b);
 
    // Include 1 initially
    let ans = 1;
 
    // Find all the prime factors of the gcd
    for (let i = 2; i * i <= gcd; i++) {
        if (gcd % i == 0) {
            ans++;
            while (gcd % i == 0)
                gcd = parseInt(gcd / i);
        }
    }
 
    // If gcd is prime
    if (gcd != 1)
        ans++;
 
    // Return the required answer
    return ans;
}
 
// Driver code
    let a = 12, b = 18;
 
    document.write(maxCommonFactors(a, b));
 
</script>

3

Complejidad de tiempo: O((log(min(a, b))) ² ), donde a y b son dos parámetros de gcd

Espacio Auxiliar: O(1)