数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究使用初中程序查找两数最大公因数 (GCD) 或最大公约数 (HCF) 的程序
在本教程中，我们将讨论使用中学流程查找两数最大公因数 (GCD) 或最大公约数 (HCF) 的程序。
为此，我们将得到两个数字。我们的任务是找出给定值的 GCD（最大公因数）或 HCF（最大公约数）。
示例
#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;
//structure to store factorization
typedef struct{
int size;
int factor[MAXFACTORS + 1];
int exponent[MAXFACTORS + 1];
} FACTORIZATION;
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++;
n = n / i;
}
if (c > 0) {
factorization->exponent[k] = c;
factorization->factor[k] = i;
k++;
}
}
factorization->size = k - 1;
}
//printing 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";
}
}
//gcd using Middle School procedure
int gcdMiddleSchoolProcedure(int m, int n){
FACTORIZATION mFactorization, nFactorization;
int r, mi, ni, i, k, x = 1, j;
FindFactorization(m, &mFactorization);
DisplayFactorization(m, mFactorization);
FindFactorization(n, &nFactorization);
DisplayFactorization(n, nFactorization);
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{
min = mFactorization.exponent[i] > nFactorization.exponent[j] ? nFactorization.exponent[j] : mFactorization.exponent[i];
x = x * mFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
int main(){
int m = 10, n = 15;
cout << "GCD(" << m << ", " << n << ") = " << gcdMiddleSchoolProcedure(m, n);
return (0);
}输出
GCD(10, 15) = Prime factor of << x << = 1*2*5 Prime factor of << x << = 1*3*5 5
更新于：09-Sep-2020
1K+ 浏览
广告