Factores primos comunes de dos números

Dados dos enteros  y  , la tarea es encontrar los divisores primos comunes de estos números.
Ejemplos: 
 

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

Enfoque ingenuo: itere de 1 a min (A, B) y verifique si i es primo y un factor de A y B , si es así, muestre el número.
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.

Enfoque eficiente para consultas múltiples: la solución anterior se puede optimizar aún más si hay consultas múltiples para factores comunes. La idea se basa en la factorización prima usando Sieve O(log n) para consultas múltiples .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN   100001
 
bool prime[MAXN];
void SieveOfEratosthenes()
{
 
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
 
    memset(prime, true, sizeof(prime));
 
    // 0 and 1 are not prime numbers
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p <= MAXN; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p as non-prime
            for (int i = p * p; i <= MAXN; i += p)
                prime[i] = false;
        }
    }
}
 
// Find the common prime divisors
void common_prime(int a, int b)
{
 
    // Get the GCD of the given numbers
    int gcd = __gcd(a, b);
 
    // Find the prime divisors of the gcd
    for (int i = 2; i <= (gcd); i++) {
 
        // If i is prime and a divisor of gcd
        if (prime[i] && gcd % i == 0) {
            cout << i << " ";
        }
    }
}
 
// Driver code
int main()
{
    // Create the Sieve
    SieveOfEratosthenes();
 
    int a = 6, b = 12;
 
    common_prime(a, b);
    return 0;
}

//Java implementation of above approach
 
class GFG {
 
static final int MAXN = 100001;
static boolean prime[] = new boolean[MAXN];
 
static void SieveOfEratosthenes()
{
 
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
 
        for(int i = 0;i<prime.length;i++)
            prime[i]=true;
 
    // 0 and 1 are not prime numbers
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p < MAXN; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p as non-prime
            for (int i = p * p; i < MAXN; i += p)
                prime[i] = false;
        }
    }
}
 
// Find the common prime divisors
static void common_prime(int a, int b)
{
 
    // Get the GCD of the given numbers
    int gcd = (int) __gcd(a, b);
 
    // Find the prime divisors of the gcd
    for (int i = 2; i <= (gcd); i++) {
 
        // If i is prime and a divisor of gcd
        if (prime[i] && gcd % i == 0) {
            System.out.print(i + " ");
        }
    }
}
static long __gcd(long a, long b) 
{ 
    if (a == 0) 
        return b; 
    return __gcd(b % a, a); 
}
// Driver code
    public static void main(String[] args) {
        // Create the Sieve
    SieveOfEratosthenes();
 
    int a = 6, b = 12;
 
    common_prime(a, b);
    }
}
 
/*This code is contributed by 29AjayKumar*/

# Python implementation of above approach
from math import gcd, sqrt
 
# Create a boolean array "prime[0..n]"
# and initialize all entries it as true.
# A value in prime[i] will finally be
# false if i is Not a prime, else true.
prime = [True] * 100001
 
def SieveOfEratosthenes() :
     
    # 0 and 1 are not prime numbers
    prime[0] = False
    prime[1] = False
     
    for p in range(2, int(sqrt(100001)) + 1) :
 
        # If prime[p] is not changed,
        # then it is a prime
        if prime[p] == True :
 
            # Update all multiples of
            # p as non-prime
            for i in range(p**2, 100001, p) :
                prime[i] = False
     
# Find the common prime divisors
def common_prime(a, b) :
 
    # Get the GCD of the given numbers
    __gcd = gcd(a, b)
 
    # Find the prime divisors of the gcd
    for i in range(2, __gcd + 1) :
  
        # If i is prime and a divisor of gcd
        if prime[i] and __gcd % i == 0 :
            print(i, end = " ")
 
# Driver code
if __name__ == "__main__" :
 
    # Create the Sieve
    SieveOfEratosthenes()
    a, b = 6, 12
     
    common_prime(a, b)
     
# This code is contributed by ANKITRAI1

//C# implementation of above approach
using System;
public class GFG {
  
    static bool []prime = new bool[100001];
    static void SieveOfEratosthenes()
    {
 
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
 
            for(int i = 0;i<prime.Length;i++)
                prime[i]=true;
 
        // 0 and 1 are not prime numbers
        prime[0] = false;
        prime[1] = false;
 
        for (int p = 2; p * p < 100001; p++) {
 
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
 
                // Update all multiples of p as non-prime
                for (int i = p * p; i < 100001; i += p)
                    prime[i] = false;
            }
        }
    }
 
    // Find the common prime divisors
    static void common_prime(int a, int b)
    {
 
        // Get the GCD of the given numbers
        int gcd = (int) __gcd(a, b);
 
        // Find the prime divisors of the gcd
        for (int i = 2; i <= (gcd); i++) {
 
            // If i is prime and a divisor of gcd
            if (prime[i] && gcd % i == 0) {
                Console.Write(i + " ");
            }
        }
    }
    static long __gcd(long a, long b) 
    { 
        if (a == 0) 
            return b; 
        return __gcd(b % a, a); 
    }
    // Driver code
    public static void Main() {
        // Create the Sieve
    SieveOfEratosthenes();
  
    int a = 6, b = 12;
  
    common_prime(a, b);
    }
}
  
/*This code is contributed by 29AjayKumar*/

<script>
// Javascript program to implement the above approach
 
MAXN = parseInt(100001);
prime = new Array(MAXN);
 
function __gcd(a, b) 
{ 
    if (a == 0) 
        return b; 
    return __gcd(b % a, a); 
}
function SieveOfEratosthenes()
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
 
    prime.fill(true);
 
    // 0 and 1 are not prime numbers
    prime[0] = false;
    prime[1] = false;
 
    for (var p = 2; p * p <= MAXN; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p as non-prime
            for (var i = p * p; i <= MAXN; i += p)
                prime[i] = false;
        }
    }
}
 
// Find the common prime divisors
function common_prime( a, b)
{
 
    // Get the GCD of the given numbers
    var gcd = __gcd(a, b);
 
    // Find the prime divisors of the gcd
    for (var i = 2; i <= (gcd); i++) {
 
        // If i is prime and a divisor of gcd
        if (prime[i] && gcd % i == 0) {
            document.write( i + " ");
       }
    }
}
 
 
SieveOfEratosthenes();
var a = 6, b = 12;
common_prime(a, b);
 
//This code is contributed by SoumikModnal
</script>

2 3