Contar factores primos comunes de dos números

Dados dos enteros  y  , la tarea es encontrar el número de factores comunes de dos números donde los factores son primos.
Ejemplos: 
 

Entrada: A = 6, B = 12 
Salida: 2 
2 y 3 son los únicos divisores primos comunes de 6 y 12
Entrada: A = 4, B = 8 
Salida: 1 
 

Enfoque ingenuo: iterar de 1 a min (A, B) y verificar si i es primo y un factor de A y B , en caso afirmativo, incremente el contador.
El enfoque eficiente es hacer lo siguiente: 
 

1. Encuentra el máximo común divisor (mcd) de los números dados.
2. Encuentra los factores primos del GCD.

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to count common prime factors
// of a and b.
#include <bits/stdc++.h>
using namespace std;
 
// A function to count all prime factors of
// a given number x
int countPrimeFactors(int x)
{
    int res = 0;
    if (x % 2 == 0) {
        res++;
 
        // Print the number of 2s that divide x
        while (x % 2 == 0)
            x = x / 2;
    }
 
    // x must be odd at this point.  So we
    // can skip one element (Note i = i +2)
    for (int i = 3; i <= sqrt(x); i = i + 2) {
        if (x % i == 0) {
 
            // While i divides x, print i and
            // divide x
            res++;
            while (x % i == 0)
                x = x / i;
        }
    }
 
    // This condition is to handle the case
    // when x is a prime number greater than 2
    if (x > 2)
        res++;
    return res;
}
 
// Count of common prime factors
int countCommonPrimeFactors(int a, int b)
{
    // Get the GCD of the given numbers
    int gcd = __gcd(a, b);
 
    // Count prime factors in GCD
    return countPrimeFactors(gcd);
}
 
// Driver code
int main()
{
    int a = 6, b = 12;
    cout << countCommonPrimeFactors(a, b);
    return 0;
}

// C program to count common prime factors
// of a and b.
#include <stdio.h>
#include <math.h>
 
// A function to count all prime factors of
// a given number x
int countPrimeFactors(int x)
{
    int res = 0;
    if (x % 2 == 0) {
        res++;
       
        // Print the number of 2s that divide x
        while (x % 2 == 0)
            x = x / 2;
    }
 
    // x must be odd at this point.  So we
    // can skip one element (Note i = i +2)
    for (int i = 3; i <= sqrt(x); i = i + 2) {
        if (x % i == 0) {
 
            // While i divides x, print i and
            // divide x
            res++;
            while (x % i == 0)
                x = x / i;
        }
    }
 
    // This condition is to handle the case
    // when x is a prime number greater than 2
    if (x > 2)
        res++;
    return res;
}
 
// Count of common prime factors
int countCommonPrimeFactors(int a, int b)
{
    int gcd, i;
   
    // Get the GCD of the given numbers
    for(i = 1; i <= a && i <= b; ++i)
    {
        // Checks if i is factor of both integers
        if(a % i == 0 && b % i == 0)
            gcd = i;
    }
 
    // Count prime factors in GCD
    return countPrimeFactors(gcd);
}
 
// Driver code
int main()
{
    int a = 6, b = 12;
    printf("%d",countCommonPrimeFactors(a, b));
    return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java  program to count common prime factors
 // of a and b.
 
import java.io.*;
 
class GFG {
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
        
        // base case
        if (a == b)
            return a;
        
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
        return __gcd(a, b-a);
    }
// A function to count all prime factors of
// a given number x
 static int countPrimeFactors(int x)
{
    int res = 0;
    if (x % 2 == 0) {
        res++;
 
        // Print the number of 2s that divide x
        while (x % 2 == 0)
            x = x / 2;
    }
 
    // x must be odd at this point. So we
    // can skip one element (Note i = i +2)
    for (int i = 3; i <= Math.sqrt(x); i = i + 2) {
        if (x % i == 0) {
 
            // While i divides x, print i and
            // divide x
            res++;
            while (x % i == 0)
                x = x / i;
        }
    }
 
    // This condition is to handle the case
    // when x is a prime number greater than 2
    if (x > 2)
        res++;
    return res;
}
 
// Count of common prime factors
static int countCommonPrimeFactors(int a, int b)
{
    // Get the GCD of the given numbers
    int gcd = __gcd(a, b);
 
    // Count prime factors in GCD
    return countPrimeFactors(gcd);
}
 
// Driver code
 
 
    public static void main (String[] args) {
    int a = 6, b = 12;
    System.out.println(countCommonPrimeFactors(a, b));
    }
}
// This code is contributed by inder_verma..

# Python 3 program to count common prime
# factors of a and b.
from math import sqrt,gcd
 
# A function to count all prime
# factors of a given number x
def countPrimeFactors(x):
    res = 0
    if (x % 2 == 0):
        res += 1
 
        # Print the number of 2s that divide x
        while (x % 2 == 0):
            x = x / 2
 
    # x must be odd at this point. So we
    # can skip one element (Note i = i +2)
    k = int(sqrt(x)) + 1
    for i in range(3, k, 2):
        if (x % i == 0):
             
            # While i divides x, print i
            # and divide x
            res += 1
            while (x % i == 0):
                x = x / i
     
    # This condition is to handle the
    # case when x is a prime number
    # greater than 2
    if (x > 2):
        res += 1
    return res
 
# Count of common prime factors
def countCommonPrimeFactors(a, b):
     
    # Get the GCD of the given numbers
    gcd__ = gcd(a, b)
 
    # Count prime factors in GCD
    return countPrimeFactors(gcd__)
 
# Driver code
if __name__ == '__main__':
    a = 6
    b = 12
    print(countCommonPrimeFactors(a, b))
     
# This code is contributed by
# Surendra_Gangwar

// C# program to count common prime factors
// of a and b.
 
using System ;
 
class GFG {
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
        return b;
        if (b == 0)
        return a;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
        return __gcd(a, b-a);
    }
    // A function to count all prime factors of
    // a given number x
    static int countPrimeFactors(int x)
    {
        int res = 0;
        if (x % 2 == 0) {
            res++;
     
            // Print the number of 2s that divide x
            while (x % 2 == 0)
                x = x / 2;
        }
     
        // x must be odd at this point. So we
        // can skip one element (Note i = i +2)
        for (int i = 3; i <= Math.Sqrt(x); i = i + 2) {
            if (x % i == 0) {
     
                // While i divides x, print i and
                // divide x
                res++;
                while (x % i == 0)
                    x = x / i;
            }
        }
     
        // This condition is to handle the case
        // when x is a prime number greater than 2
        if (x > 2)
            res++;
        return res;
    }
     
    // Count of common prime factors
    static int countCommonPrimeFactors(int a, int b)
    {
        // Get the GCD of the given numbers
        int gcd = __gcd(a, b);
     
        // Count prime factors in GCD
        return countPrimeFactors(gcd);
    }
     
    // Driver code
    public static void Main() {
    int a = 6, b = 12;
     
    Console.WriteLine(countCommonPrimeFactors(a, b));
    }
    // This code is contributed by Ryuga
}

<?php
// PHP program to count common
// prime factors of a and b.
 
// Recursive function to return
// gcd of a and b
function __gcd($a, $b)
{
    // Everything divides 0
    if ($a == 0)
        return $b;
    if ($b == 0)
        return $a;
     
    // base case
    if ($a == $b)
        return $a;
     
    // a is greater
    if ($a > $b)
        return __gcd(($a - $b), $b);
    return __gcd($a, ($b - $a));
}
 
// A function to count all prime
// factors of a given number x
function countPrimeFactors($x)
{
    $res = 0;
    if ($x % 2 == 0)
    {
        $res++;
 
        // Print the number of 2s that
        // divide x
        while ($x % 2 == 0)
            $x = $x / 2;
    }
 
    // x must be odd at this point. So we
    // can skip one element (Note i = i +2)
    for ($i = 3; $i <= sqrt($x); $i = $i + 2)
    {
        if ($x % $i == 0)
        {
 
            // While i divides x, print i
            // and divide x
            $res++;
            while ($x % $i == 0)
                $x = $x / $i;
        }
    }
 
    // This condition is to handle the case
    // when x is a prime number greater than 2
    if ($x > 2)
        $res++;
    return $res;
}
 
// Count of common prime factors
function countCommonPrimeFactors($a, $b)
{
    // Get the GCD of the given numbers
    $gcd = __gcd($a, $b);
 
    // Count prime factors in GCD
    return countPrimeFactors($gcd);
}
 
// Driver code
$a = 6;
$b = 12;
 
echo (countCommonPrimeFactors($a, $b));
 
// This code is contributed by akt_mit..
?>

<script>
 
    // Javascript program to count
    // common prime factors of a and b.
     
    // Recursive function to return
    // gcd of a and b
    function __gcd(a, b)
    {
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
           
        // base case
        if (a == b)
            return a;
           
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
        return __gcd(a, b-a);
    }
    // A function to count all prime factors of
    // a given number x
    function countPrimeFactors(x)
    {
        let res = 0;
        if (x % 2 == 0) {
            res++;
       
            // Print the number of 2s that divide x
            while (x % 2 == 0)
                x = parseInt(x / 2, 10);
        }
       
        // x must be odd at this point. So we
        // can skip one element (Note i = i +2)
        for (let i = 3; i <= Math.sqrt(x); i = i + 2)
        {
            if (x % i == 0) {
       
                // While i divides x, print i and
                // divide x
                res++;
                while (x % i == 0)
                    x = parseInt(x / i, 10);
            }
        }
       
        // This condition is to handle the case
        // when x is a prime number greater than 2
        if (x > 2)
            res++;
        return res;
    }
       
    // Count of common prime factors
    function countCommonPrimeFactors(a, b)
    {
        // Get the GCD of the given numbers
        let gcd = __gcd(a, b);
       
        // Count prime factors in GCD
        return countPrimeFactors(gcd);
    }
     
    let a = 6, b = 12;
       
    document.write(countCommonPrimeFactors(a, b));
     
</script>

2

Complejidad de tiempo: O(sqrtn*logn)

Espacio Auxiliar: O(1)

Si hay múltiples consultas para contar divisores comunes, podemos optimizar aún más el código anterior usando la factorización prima usando Sieve O (log n) para múltiples consultas