Cree un gráfico conectando divisores de N a M y encuentre el camino más corto

Dados dos números naturales N y M , cree un gráfico usando estos dos números naturales usando la relación de que un número está conectado a su factor más grande que no sea él mismo. La tarea es encontrar el camino más corto entre estos dos números después de crear un gráfico.

Ejemplos:

Entrada: N = 6, M = 18
Salida: 6 <–> 3 <–> 9 <–> 18
Explicación:
Para N = 6, la conexión del gráfico es:
6 — 3 — 1
Para N = 18, la conexión de el gráfico es:
18 — 9 — 3 — 1
Combinando los dos gráficos anteriores, el camino más corto está dado por:
6 — 3 — 9 — 18

Entrada: N = 4, M = 8
Salida: 4 <–> 8

Enfoque: la idea es encontrar los factores más grandes de cada número que no sea él mismo y crear un gráfico conectando estos factores y luego encontrar el camino más corto entre ellos. A continuación se muestran los pasos:

  1. Encuentre el factor común más grande de M y guárdelo y configúrelo como M .
  2. Ahora, hasta que M no sea igual a 1, siga repitiendo los pasos anteriores y almacene los factores generados en una array mfactor[] .
  3. Repita los pasos 1 y 2 tomando N como el número y almacene los factores generados en una array nfactor[] .
  4. Ahora, recorra las arrays mfactor[] y mfactor[] e imprima la ruta más corta.

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

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the number is
// prime or not
int isprm(int n)
{
    // Base Cases
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
 
    // Iterate till [5, sqrt(N)] to
    // detect primarility of numbers
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    return 1;
}
 
// Function to print the shortest path
void shortestpath(int m, int n)
{
    // Use vector to store the factor
    // of m and n
    vector<int> mfactor, nfactor;
 
    // Use map to check if largest common
    // factor previously present or not
    map<int, int> fre;
 
    // First store m
    mfactor.push_back(m);
    fre[m] = 1;
 
    while (m != 1) {
 
        // Check whether m is prime or not
        if (isprm(m)) {
            mfactor.push_back(1);
            fre[1] = 1;
            m = 1;
        }
 
        // Largest common factor of m
        else {
            for (int i = 2;
                 i <= sqrt(m); i++) {
 
                // If m is divisible by i
                if (m % i == 0) {
 
                    // Store the largest
                    // common factor
                    mfactor.push_back(m / i);
                    fre[m / i] = 1;
                    m = (m / i);
                    break;
                }
            }
        }
    }
 
    // For number n
    nfactor.push_back(n);
 
    while (fre[n] != 1) {
 
        // Check whether n is prime
        if (isprm(n)) {
            nfactor.push_back(1);
            n = 1;
        }
 
        // Largest common factor of n
        else {
            for (int i = 2;
                 i <= sqrt(n); i++) {
                if (n % i == 0) {
 
                    // Store the largest
                    // common factor
                    nfactor.push_back(n / i);
                    n = (n / i);
                    break;
                }
            }
        }
    }
 
    // Print the path
    // Print factors from m
    for (int i = 0;
         i < mfactor.size(); i++) {
 
        // To avoid duplicate printing
        // of same element
        if (mfactor[i] == n)
            break;
 
        cout << mfactor[i]
             << " <--> ";
    }
 
    // Print the factors from n
    for (int i = nfactor.size() - 1;
         i >= 0; i--) {
        if (i == 0)
            cout << nfactor[i];
        else
            cout << nfactor[i]
                 << " <--> ";
    }
}
 
// Driver Code
int main()
{
    // Given N and M
    int m = 18, n = 19;
 
    // Function Call
    shortestpath(m, n);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check the number is
// prime or not
static int isprm(int n)
{
     
    // Base Cases
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
 
    // Iterate till [5, Math.sqrt(N)] to
    // detect primarility of numbers
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
         
    return 1;
}
 
// Function to print the shortest path
static void shortestpath(int m, int n)
{
     
    // Use vector to store the factor
    // of m and n
    Vector<Integer> mfactor = new Vector<>();
    Vector<Integer> nfactor = new Vector<>();
 
    // Use map to check if largest common
    // factor previously present or not
    HashMap<Integer, Integer> fre = new HashMap<>();
 
    // First store m
    mfactor.add(m);
    fre.put(m, 1);
 
    while (m != 1)
    {
 
        // Check whether m is prime or not
        if (isprm(m) != 0)
        {
            mfactor.add(1);
            fre.put(1, 1);
            m = 1;
        }
 
        // Largest common factor of m
        else
        {
            for(int i = 2;
                    i <= Math.sqrt(m); i++)
            {
 
                // If m is divisible by i
                if (m % i == 0)
                {
                     
                    // Store the largest
                    // common factor
                    mfactor.add(m / i);
                    fre.put(m / i, 1);
                    m = (m / i);
                    break;
                }
            }
        }
    }
 
    // For number n
    nfactor.add(n);
 
    while (fre.containsKey(n) && fre.get(n) != 1)
    {
         
        // Check whether n is prime
        if (isprm(n) != 0)
        {
            nfactor.add(1);
            n = 1;
        }
 
        // Largest common factor of n
        else
        {
            for(int i = 2;
                    i <= Math.sqrt(n); i++)
            {
                if (n % i == 0)
                {
 
                    // Store the largest
                    // common factor
                    nfactor.add(n / i);
                    n = (n / i);
                    break;
                }
            }
        }
    }
 
    // Print the path
    // Print factors from m
    for(int i = 0; i < mfactor.size(); i++)
    {
         
        // To astatic void duplicate printing
        // of same element
        if (mfactor.get(i) == n)
            break;
 
        System.out.print(mfactor.get(i) +
                         " <--> ");
    }
 
    // Print the factors from n
    for(int i = nfactor.size() - 1;
            i >= 0; i--)
    {
        if (i == 0)
            System.out.print(nfactor.get(i));
        else
            System.out.print(nfactor.get(i) +
                             " <--> ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N and M
    int m = 18, n = 19;
 
    // Function call
    shortestpath(m, n);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
import math
 
# Function to check the number is
# prime or not
def isprm(n):
 
    # Base Cases
    if (n <= 1):
        return 0
    if (n <= 3):
        return 1
    if (n % 2 == 0 or n % 3 == 0):
        return 0
 
    # Iterate till [5, sqrt(N)] to
    # detect primarility of numbers
    i = 5
    while i * i <= n:
        if (n % i == 0 or n % (i + 2) == 0):
            return 0
             
        i += 6
         
    return 1
 
# Function to print the shortest path
def shortestpath(m, n):
 
    # Use vector to store the factor
    # of m and n
    mfactor = []
    nfactor = []
 
    # Use map to check if largest common
    # factor previously present or not
    fre = dict.fromkeys(range(n + 1), 0)
 
    # First store m
    mfactor.append(m)
    fre[m] = 1
 
    while (m != 1):
 
        # Check whether m is prime or not
        if (isprm(m)):
            mfactor.append(1)
            fre[1] = 1
            m = 1
 
        # Largest common factor of m
        else:
            sqt = (int)(math.sqrt(m))
            for i in range(2, sqt + 1):
 
                # If m is divisible by i
                if (m % i == 0):
 
                    # Store the largest
                    # common factor
                    mfactor.append(m // i)
                    fre[m // i] = 1
                    m = (m // i)
                    break
 
    # For number n
    nfactor.append(n)
 
    while (fre[n] != 1):
 
        # Check whether n is prime
        if (isprm(n)):
            nfactor.append(1)
            n = 1
         
        # Largest common factor of n
        else:
            sqt = (int)(math.sqrt(n))
            for i in range(2, sqt + 1):
                if (n % i == 0):
 
                    # Store the largest
                    # common factor
                    nfactor.append(n // i)
                    n = (n // i)
                    break
 
    # Print the path
    # Print factors from m
    for i in range(len(mfactor)):
 
        # To avoid duplicate printing
        # of same element
        if (mfactor[i] == n):
            break
 
        print(mfactor[i], end = " <--> ")
 
    # Print the factors from n
    for i in range(len(nfactor) - 1, -1, -1):
        if (i == 0):
            print (nfactor[i], end = "")
        else:
            print(nfactor[i], end = " <--> ")
                 
# Driver Code
if __name__ == "__main__":
     
    # Given N and M
    m = 18
    n = 19
 
    # Function call
    shortestpath(m, n)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check the number is
// prime or not
static int isprm(int n)
{
     
    // Base Cases
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
 
    // Iterate till [5, Math.Sqrt(N)] to
    // detect primarility of numbers
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
         
    return 1;
}
 
// Function to print the shortest path
static void shortestpath(int m, int n)
{
     
    // Use vector to store the factor
    // of m and n
    List<int> mfactor = new List<int>();
    List<int> nfactor = new List<int>();
 
    // Use map to check if largest common
    // factor previously present or not
    Dictionary<int,
               int> fre = new Dictionary<int,
                                         int>();
 
    // First store m
    mfactor.Add(m);
    fre.Add(m, 1);
 
    while (m != 1)
    {
 
        // Check whether m is prime or not
        if (isprm(m) != 0)
        {
            mfactor.Add(1);
            if(!fre.ContainsKey(1))
                fre.Add(1, 1);
                 
            m = 1;
        }
 
        // Largest common factor of m
        else
        {
            for(int i = 2;
                    i <= Math.Sqrt(m); i++)
            {
 
                // If m is divisible by i
                if (m % i == 0)
                {
                     
                    // Store the largest
                    // common factor
                    mfactor.Add(m / i);
                    if(!fre.ContainsKey(m/i))
                        fre.Add(m / i, 1);
                         
                    m = (m / i);
                    break;
                }
            }
        }
    }
 
    // For number n
    nfactor.Add(n);
 
    while (fre.ContainsKey(n) && fre[n] != 1)
    {
         
        // Check whether n is prime
        if (isprm(n) != 0)
        {
            nfactor.Add(1);
            n = 1;
        }
 
        // Largest common factor of n
        else
        {
            for(int i = 2;
                    i <= Math.Sqrt(n); i++)
            {
                if (n % i == 0)
                {
 
                    // Store the largest
                    // common factor
                    nfactor.Add(n / i);
                    n = (n / i);
                    break;
                }
            }
        }
    }
 
    // Print the path
    // Print factors from m
    for(int i = 0; i < mfactor.Count; i++)
    {
         
        // To astatic void duplicate printing
        // of same element
        if (mfactor[i] == n)
            break;
 
        Console.Write(mfactor[i] +
                        " <--> ");
    }
 
    // Print the factors from n
    for(int i = nfactor.Count - 1;
            i >= 0; i--)
    {
        if (i == 0)
            Console.Write(nfactor[i]);
        else
            Console.Write(nfactor[i] +
                            " <--> ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N and M
    int m = 18, n = 19;
 
    // Function call
    shortestpath(m, n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

// Javascript program for the above approach
 
// Function to check the number is
// prime or not
function isprm(n)
{
    // Base Cases
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
 
    // Iterate till [5, sqrt(N)] to
    // detect primarility of numbers
    for (let i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    return 1;
}
 
// Function to print the shortest path
function shortestpath(m, n)
{
    // Use vector to store the factor
    // of m and n
    let mfactor = new Array()
    let nfactor = new Array()
 
    // Use map to check if largest common
    // factor previously present or not
    let fre = new Map();
 
    // First store m
    mfactor.push(m);
    fre[m] = 1;
 
    while (m != 1) {
 
        // Check whether m is prime or not
        if (isprm(m)) {
            mfactor.push(1);
            fre[1] = 1;
            m = 1;
        }
 
        // Largest common factor of m
        else {
            for (let i = 2;
                i <= Math.sqrt(m); i++) {
 
                // If m is divisible by i
                if (m % i == 0) {
 
                    // Store the largest
                    // common factor
                    mfactor.push(m / i);
                    fre[m / i] = 1;
                    m = (m / i);
                    break;
                }
            }
        }
    }
 
    // For number n
    nfactor.push(n);
 
    while (fre[n] != 1) {
 
        // Check whether n is prime
        if (isprm(n)) {
            nfactor.push(1);
            n = 1;
        }
 
        // Largest common factor of n
        else {
            for (let i = 2;
                i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
 
                    // Store the largest
                    // common factor
                    nfactor.push(n / i);
                    n = (n / i);
                    break;
                }
            }
        }
    }
 
    // Print the path
    // Print factors from m
    for (let i = 0;
        i < mfactor.length; i++) {
 
        // To avoid duplicate printing
        // of same element
        if (mfactor[i] == n)
            break;
 
        document.write(mfactor[i] + " <--> ");
    }
 
    // Print the factors from n
    for (let i = nfactor.length - 1;
        i >= 0; i--) {
        if (i == 0)
            document.write(nfactor[i]);
        else
            document.write(nfactor[i] + " <--> ");
    }
}
 
// Driver Code
 
// Given N and M
let m = 18, n = 19;
 
// Function Call
shortestpath(m, n);
 
// This code is contributed by _saurabh_jaiswal
Producción: 

18 <--> 9 <--> 3 <--> 1 <--> 19

Complejidad de tiempo: O(log (max(M, N))
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por rubaimandal3 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 *