给定两个正整数M和N，任务是找到 最大公约数（GCD） 使用中学程序。 注： 两个整数的GCD是除以两个整数的最大正整数。 例如：
null
Input: m = 12, n = 14Output: 2Prime factor of 12 = 1*2*2*3Prime factor of 14 = 1*2*7GCD(12, 14) = 2Input: m = 5, n = 10Output: 5Prime factor of 10 = 1*2*5Prime factor of 5 = 1*5GCD(5, 10) = 5
使用中学程序GCD（m，n）查找GCD的算法：
- 求m的素因式分解。
- 求n的素因式分解。
- 找出所有共同的素因子。
- 计算所有公共素数因子的乘积，并将其作为gcd（m，n）返回。
下面是上述算法的实现：
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 << "" ; } } // 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> |
输出：
Prime factor of 10 = 1*2*5Prime factor of 15 = 1*3*5GCD(10, 15) = 5
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
