Dados dos enteros positivos M y N, la tarea es encontrar el máximo común divisor (MCD) utilizando el Procedimiento de la escuela intermedia.
Nota: MCD de dos enteros es el entero positivo más grande que divide a ambos enteros.
Ejemplos:
Input: m = 12, n = 14 Output: 2 Prime factor of 12 = 1*2*2*3 Prime factor of 14 = 1*2*7 GCD(12, 14) = 2 Input: m = 5, n = 10 Output: 5 Prime factor of 10 = 1*2*5 Prime factor of 5 = 1*5 GCD(5, 10) = 5
El algoritmo para encontrar GCD usando el procedimiento de Middle School GCD(m, n):
- Encuentre la descomposición en factores primos de m.
- Encuentre la descomposición en factores primos de n.
- Encuentra todos los factores primos comunes.
- Calcule el producto de todos los factores primos comunes y devuélvalo como mcd(m, n).
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ implementation of above algorithm
#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;
// struct to store factorization of m and n
typedef struct
{
int size;
int factor[MAXFACTORS + 1];
int exponent[MAXFACTORS + 1];
} FACTORIZATION;
// Function to find the factorization of M and N
void FindFactorization(int x, FACTORIZATION* factorization)
{
int i, j = 1;
int n = x, c = 0;
int k = 1;
factorization->factor[0] = 1;
factorization->exponent[0] = 1;
for (i = 2; i <= n; i++) {
c = 0;
while (n % i == 0) {
c++;
// factorization->factor[j]=i;
n = n / i;
// j++;
}
if (c > 0) {
factorization->exponent[k] = c;
factorization->factor[k] = i;
k++;
}
}
factorization->size = k - 1;
}
// Function to print the factors
void DisplayFactorization(int x, FACTORIZATION factorization)
{
int i;
cout << "Prime factor of << x << = ";
for (i = 0; i <= factorization.size; i++) {
cout << factorization.factor[i];
if (factorization.exponent[i] > 1)
cout << "^" << factorization.exponent[i];
if (i < factorization.size)
cout << "*";
else
cout << "\n";
}
}
// function to find the gcd using Middle School procedure
int gcdMiddleSchoolProcedure(int m, int n)
{
FACTORIZATION mFactorization, nFactorization;
int r, mi, ni, i, k, x = 1, j;
// Step 1.
FindFactorization(m, &mFactorization);
DisplayFactorization(m, mFactorization);
// Step 2.
FindFactorization(n, &nFactorization);
DisplayFactorization(n, nFactorization);
// Steps 3 and 4.
// Procedure algorithm for computing the
// greatest common divisor.
int min;
i = 1;
j = 1;
while (i <= mFactorization.size && j <= nFactorization.size) {
if (mFactorization.factor[i] < nFactorization.factor[j])
i++;
else if (nFactorization.factor[j] < mFactorization.factor[i])
j++;
else /* if arr1[i] == arr2[j] */
{
min = mFactorization.exponent[i] > nFactorization.exponent[j]
? nFactorization.exponent[j]
: mFactorization.exponent[i];
x = x * mFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
// Driver code
int main()
{
int m = 10, n = 15;
cout << "GCD(" << m << ", " << n << ") = "
<< gcdMiddleSchoolProcedure(m, n);
return (0);
}
Java
// Java implementation of above algorithm
class GFG
{
static final int MAXFACTORS = 1024 ;
// class to store factorization
// of m and n
static class FACTORIZATION
{
int size;
int factor[] = new int[MAXFACTORS + 1];
int exponent[] = new int[MAXFACTORS + 1];
}
// Function to find the
// factorization of M and N
static void FindFactorization(int x, FACTORIZATION
factorization)
{
int i, j = 1;
int n = x, c = 0;
int k = 1;
factorization.factor[0] = 1;
factorization.exponent[0] = 1;
for (i = 2; i <= n; i++)
{
c = 0;
while (n % i == 0)
{
c++;
// factorization.factor[j]=i;
n = n / i;
// j++;
}
if (c > 0)
{
factorization.exponent[k] = c;
factorization.factor[k] = i;
k++;
}
}
factorization.size = k - 1;
}
// Function to print the factors
static void DisplayFactorization(int x, FACTORIZATION
factorization)
{
int i;
System.out.print("Prime factor of " + x + " = ");
for (i = 0;
i <= factorization.size; i++)
{
System.out.print(factorization.factor[i]);
if (factorization.exponent[i] > 1)
System.out.print( "^" +
factorization.exponent[i]);
if (i < factorization.size)
System.out.print("*");
else
System.out.println( );
}
}
// function to find the gcd
// using Middle School procedure
static int gcdMiddleSchoolProcedure(int m, int n)
{
FACTORIZATION mFactorization = new FACTORIZATION();
FACTORIZATION nFactorization = new FACTORIZATION();
int r, mi, ni, i, k, x = 1, j;
// Step 1.
FindFactorization(m, mFactorization);
DisplayFactorization(m, mFactorization);
// Step 2.
FindFactorization(n, nFactorization);
DisplayFactorization(n, nFactorization);
// Steps 3 and 4.
// Procedure algorithm for computing the
// greatest common divisor.
int min;
i = 1;
j = 1;
while (i <= mFactorization.size &&
j <= nFactorization.size)
{
if (mFactorization.factor[i] <
nFactorization.factor[j])
i++;
else if (nFactorization.factor[j] <
mFactorization.factor[i])
j++;
else /* if arr1[i] == arr2[j] */
{
min = mFactorization.exponent[i] >
nFactorization.exponent[j] ?
nFactorization.exponent[j] :
mFactorization.exponent[i];
x = x * mFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
// Driver code
public static void main(String args[])
{
int m = 10, n = 15;
System.out.print("GCD(" + m + ", " + n + ") = " +
gcdMiddleSchoolProcedure(m, n));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of above algorithm
MAXFACTORS = 1024
# class to store factorization
# of m and n
class FACTORIZATION:
def __init__(self):
self.size = 0
self.factor = [0]*(MAXFACTORS + 1)
self.exponent = [0]*(MAXFACTORS + 1)
# Function to find the
# factorization of M and N
def FindFactorization(x,factorization):
j = 1
n, c = x, 0
k = 1
factorization.factor[0] = 1
factorization.exponent[0] = 1
for i in range(2, n + 1):
c = 0
while (n % i == 0):
c+=1
# factorization.factor[j]=i;
n = n / i
# j++
if (c > 0):
factorization.exponent[k] = c
factorization.factor[k] = i
k+=1
factorization.size = k - 1
# Function to print the factors
def DisplayFactorization(x,factorization):
print("Prime factor of", x, "= ", end="")
for i in range(factorization.size + 1):
print(factorization.factor[i], end = "")
if (factorization.exponent[i] > 1):
print( "^", factorization.exponent[i], sep = "", end = "")
if (i < factorization.size):
print("*", end = "")
else:
print()
# function to find the gcd
# using Middle School procedure
def gcdMiddleSchoolProcedure(m,n):
mFactorization = FACTORIZATION()
nFactorization = FACTORIZATION()
x = 1
# Step 1.
FindFactorization(m, mFactorization)
DisplayFactorization(m, mFactorization)
# Step 2.
FindFactorization(n, nFactorization)
DisplayFactorization(n, nFactorization)
# Steps 3 and 4.
# Procedure algorithm for computing the
# greatest common divisor.
i = 1
j = 1
while (i <= mFactorization.size and j <= nFactorization.size):
if (mFactorization.factor[i] < nFactorization.factor[j]):
i+=1
elif (nFactorization.factor[j] < mFactorization.factor[i]):
j+=1
else: # if arr1[i] == arr2[j]
if mFactorization.exponent[i] > nFactorization.exponent[j]:
Min = nFactorization.exponent[j]
else:
Min = mFactorization.exponent[i]
x = x * mFactorization.factor[i] * Min
i+=1
j+=1
return x
# Driver code
m, n = 10, 15
print("GCD(", m, ", ", n, ") = ", gcdMiddleSchoolProcedure(m, n), sep = "")
# This code is contributed by suresh07.
C#
// C# implementation of above algorithm
using System;
public class GFG
{
static readonly int MAXFACTORS = 1024 ;
// class to store factorization
// of m and n
public class FACTORIZATION
{
public int size;
public int []factor = new int[MAXFACTORS + 1];
public int []exponent = new int[MAXFACTORS + 1];
}
// Function to find the
// factorization of M and N
static void FindFactorization(int x, FACTORIZATION
factorization)
{
int i;
int n = x, c = 0;
int k = 1;
factorization.factor[0] = 1;
factorization.exponent[0] = 1;
for (i = 2; i <= n; i++)
{
c = 0;
while (n % i == 0)
{
c++;
// factorization.factor[j]=i;
n = n / i;
// j++;
}
if (c > 0)
{
factorization.exponent[k] = c;
factorization.factor[k] = i;
k++;
}
}
factorization.size = k - 1;
}
// Function to print the factors
static void DisplayFactorization(int x, FACTORIZATION
factorization)
{
int i;
Console.Write("Prime factor of " + x + " = ");
for (i = 0;
i <= factorization.size; i++)
{
Console.Write(factorization.factor[i]);
if (factorization.exponent[i] > 1)
Console.Write( "^" +
factorization.exponent[i]);
if (i < factorization.size)
Console.Write("*");
else
Console.WriteLine();
}
}
// function to find the gcd
// using Middle School procedure
static int gcdMiddleSchoolProcedure(int m, int n)
{
FACTORIZATION mFactorization = new FACTORIZATION();
FACTORIZATION nFactorization = new FACTORIZATION();
int i, x = 1, j;
// Step 1.
FindFactorization(m, mFactorization);
DisplayFactorization(m, mFactorization);
// Step 2.
FindFactorization(n, nFactorization);
DisplayFactorization(n, nFactorization);
// Steps 3 and 4.
// Procedure algorithm for computing the
// greatest common divisor.
int min;
i = 1;
j = 1;
while (i <= mFactorization.size &&
j <= nFactorization.size)
{
if (mFactorization.factor[i] <
nFactorization.factor[j])
i++;
else if (nFactorization.factor[j] <
mFactorization.factor[i])
j++;
else /* if arr1[i] == arr2[j] */
{
min = mFactorization.exponent[i] >
nFactorization.exponent[j] ?
nFactorization.exponent[j] :
mFactorization.exponent[i];
x = x * mFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
// Driver code
public static void Main(String []args)
{
int m = 10, n = 15;
Console.Write("GCD(" + m + ", " + n + ") = " +
gcdMiddleSchoolProcedure(m, n));
}
}
// This code contribut by Rajput-Ji
Javascript
<script>
// JavaScript implementation of above algorithm
let MAXFACTORS = 1024 ;
// class to store factorization
// of m and n
class FACTORIZATION
{
constructor()
{
this.size=0;;
this.factor = new Array(MAXFACTORS + 1);
this.exponent = new Array(MAXFACTORS + 1);
}
}
// Function to find the
// factorization of M and N
function FindFactorization(x,factorization)
{
let i, j = 1;
let n = x, c = 0;
let k = 1;
factorization.factor[0] = 1;
factorization.exponent[0] = 1;
for (i = 2; i <= n; i++)
{
c = 0;
while (n % i == 0)
{
c++;
// factorization.factor[j]=i;
n = n / i;
// j++;
}
if (c > 0)
{
factorization.exponent[k] = c;
factorization.factor[k] = i;
k++;
}
}
factorization.size = k - 1;
}
// Function to print the factors
function DisplayFactorization(x,factorization)
{
let i;
document.write("Prime factor of " + x + " = ");
for (i = 0;
i <= factorization.size; i++)
{
document.write(factorization.factor[i]);
if (factorization.exponent[i] > 1)
document.write( "^" +
factorization.exponent[i]);
if (i < factorization.size)
document.write("*");
else
document.write("<br>" );
}
}
// function to find the gcd
// using Middle School procedure
function gcdMiddleSchoolProcedure(m,n)
{
let mFactorization = new FACTORIZATION();
let nFactorization = new FACTORIZATION();
let r, mi, ni, i, k, x = 1, j;
// Step 1.
FindFactorization(m, mFactorization);
DisplayFactorization(m, mFactorization);
// Step 2.
FindFactorization(n, nFactorization);
DisplayFactorization(n, nFactorization);
// Steps 3 and 4.
// Procedure algorithm for computing the
// greatest common divisor.
let min;
i = 1;
j = 1;
while (i <= mFactorization.size &&
j <= nFactorization.size)
{
if (mFactorization.factor[i] <
nFactorization.factor[j])
i++;
else if (nFactorization.factor[j] <
mFactorization.factor[i])
j++;
else /* if arr1[i] == arr2[j] */
{
min = mFactorization.exponent[i] >
nFactorization.exponent[j] ?
nFactorization.exponent[j] :
mFactorization.exponent[i];
x = x * mFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
// Driver code
let m = 10, n = 15;
document.write("GCD(" + m + ", " + n + ") = " +
gcdMiddleSchoolProcedure(m, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Prime factor of 10 = 1*2*5 Prime factor of 15 = 1*3*5 GCD(10, 15) = 5
Publicación traducida automáticamente
Artículo escrito por Kamal Deep Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA