Operaciones con números primos mínimos para convertir A en B

Posted on by Rudeus Greyrat

Dados dos enteros A y B , la tarea es convertir A en B con un número mínimo de las siguientes operaciones:  

  1. Multiplica A por cualquier número primo .
  2. Divide A entre uno de sus divisores primos .

Imprime el número mínimo de operaciones requeridas.
Ejemplos: 
 

Entrada: A = 10, B = 15 
Salida: 2 
Operación 1: 10 / 2 = 5 
Operación 2: 5 * 3 = 15
Entrada: A = 9, B = 7 
Salida: 3 
 

Enfoque ingenuo: Si la descomposición en factores primos de A = p 1 q 1 * p 2 q 2 * … * p n q n . Si multiplicamos A por algún primo entonces q i para ese primo aumentará en 1 y si dividimos A por uno de sus factores primos entonces q i para ese primo disminuirá en 1 . Entonces, para un primo p si ocurre q A veces en la descomposición en factores primos de A y q B veces en la descomposición en factores primos de Bentonces solo necesitamos encontrar la suma de |q A – q B | para que todos los números primos obtengan un número mínimo de operaciones.
 

Enfoque eficiente: elimine todos los factores comunes de A y B dividiendo tanto A como B por su GCD. Si A y B no tienen factores comunes, solo necesitamos la suma de las potencias de sus factores primos para convertir A en B.
 

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

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// prime factors of a number
int countFactors(int n)
{
    int factors = 0;
 
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            n /= i;
            factors += 1;
        }
    }
 
    if (n != 1)
        factors++;
 
    return factors;
}
 
// Function to return the minimum number of
// given operations required to convert A to B
int minOperations(int A, int B)
{
    int g = __gcd(A, B); // gcd(A, B);
 
    // Eliminate the common
    // factors of A and B
    A /= g;
    B /= g;
 
    // Sum of prime factors
    return countFactors(A) + countFactors(B);
}
 
// Driver code
int main()
{
    int A = 10, B = 15;
 
    cout << minOperations(A, B);
 
    return 0;
}

Java

// Java implementation of above approach
import java .io.*;
 
class GFG
{
     
// Function to return the count of
// prime factors of a number
static int countFactors(int n)
{
    int factors = 0;
 
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            n /= i;
            factors += 1;
        }
    }
 
    if (n != 1)
        factors++;
 
        return factors;
}
 
static int __gcd(int a, int b)
{
    if (b == 0)
    return a;
    return __gcd(b, a % b);
}
 
// Function to return the minimum
// number of given operations
// required to convert A to B
static int minOperations(int A, int B)
{
    int g = __gcd(A, B); // gcd(A, B);
 
    // Eliminate the common
    // factors of A and B
    A /= g;
    B /= g;
 
    // Sum of prime factors
    return countFactors(A) + countFactors(B);
}
 
// Driver code
public static void main(String[] args)
{
    int A = 10, B = 15;
 
    System.out.println(minOperations(A, B));
}
}
 
// This code is contributed
// by Code_Mech

Python3

# Python3 implementation of above approach
 
# from math lib import sqrt
# and gcd function
from math import sqrt, gcd
 
# Function to return the count of
# prime factors of a number
def countFactors(n) :
    factors = 0;
 
    for i in range(2, int(sqrt(n)) + 1) :
        while (n % i == 0) :
            n //= i
            factors += 1
 
    if (n != 1) :
        factors += 1
 
    return factors
 
# Function to return the minimum number of
# given operations required to convert A to B
def minOperations(A, B) :
     
    g = gcd(A, B)
 
    # Eliminate the common
    # factors of A and B
    A //= g
    B //= g
 
    # Sum of prime factors
    return countFactors(A) + countFactors(B)
 
# Driver code
if __name__ == "__main__" :
 
    A, B = 10, 15
 
    print(minOperations(A, B))
 
# This code is contributed by Ryuga

C#

// C# implementation of above approach
using System;
     
class GFG
{
     
    // Function to return the count of
    // prime factors of a number
    static int countFactors(int n)
    {
        int factors = 0;
        for (int i = 2; i * i <= n; i++)
        {
            while (n % i == 0)
            {
                n /= i;
                factors += 1;
            }
        }
 
        if (n != 1)
            factors++;
 
        return factors;
    }
 
    static int __gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return __gcd(b, a % b);
    }
 
    // Function to return the minimum
    // number of given operations
    // required to convert A to B
    static int minOperations(int A, int B)
    {
        int g = __gcd(A, B); // gcd(A, B);
 
        // Eliminate the common
        // factors of A and B
        A /= g;
        B /= g;
 
        // Sum of prime factors
        return countFactors(A) + countFactors(B);
    }
 
    // Driver code
    public static void Main()
    {
        int A = 10, B = 15;
        Console.WriteLine(minOperations(A, B));
    }
}
 
// This code is contributed by
// PrinciRaj1992

PHP

<?php
// PHP implementation of above approach
 
// Function to calculate gcd
function __gcd($a, $b)
{
         
    // Everything divides 0
    if ($a == 0 || $b == 0)
        return 0;
     
    // base case
    if ($a == $b)
        return $a;
     
    // a is greater
    if ($a > $b)
        return __gcd($a - $b, $b);
             
    return __gcd($a, $b - $a);
}
 
// Function to return the count of
// prime factors of a number
function countFactors($n)
{
    $factors = 0;
 
    for ($i = 2; $i * $i <= $n; $i++)
    {
        while ($n % $i == 0)
        {
            $n /= $i;
            $factors += 1;
        }
    }
 
    if ($n != 1)
        $factors++;
 
    return $factors;
}
 
// Function to return the minimum number of
// given operations required to convert A to B
function minOperations($A, $B)
{
    $g = __gcd($A, $B); // gcd(A, B);
 
    // Eliminate the common
    // factors of A and B
    $A /= $g;
    $B /= $g;
 
    // Sum of prime factors
    return countFactors($A) +
           countFactors($B);
}
 
// Driver code
$A = 10; $B = 15;
 
echo minOperations($A, $B);
 
// This code is contributed
// by Akanksha Rai
?>

Javascript

<script>
// javascript implementation of above approach
 
    // Function to return the count of
    // prime factors of a number
    function countFactors(n) {
        var factors = 0;
 
        for (i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                n /= i;
                factors += 1;
            }
        }
 
        if (n != 1)
            factors++;
 
        return factors;
    }
 
    function __gcd(a , b) {
        if (b == 0)
            return a;
        return __gcd(b, a % b);
    }
 
    // Function to return the minimum
    // number of given operations
    // required to convert A to B
    function minOperations(A , B) {
        var g = __gcd(A, B); // gcd(A, B);
 
        // Eliminate the common
        // factors of A and B
        A /= g;
        B /= g;
 
        // Sum of prime factors
        return countFactors(A) + countFactors(B);
    }
 
    // Driver code
     
        var A = 10, B = 15;
 
        document.write(minOperations(A, B));
 
// This code contributed by Rajput-Ji
</script>
Producción: 

2

 

Complejidad del tiempo: O(sqrtn*logn)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por saurabh_shukla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *