查找两个数字的 GCD 的 C++ 程序

2024 年 8 月 28 日 | 3 分钟阅读

在本教程中，我们将编写一个 C++ 程序来查找两个数的最大公约数。

最大公约数 (GCD) 也称为最高公因数 (HCF)。

例如

36 = 2 * 2 * 3 * 3

60 = 2 * 2 * 3 * 5

这两个数的最高公因数是 2、2 和 3。

所以，这两个数的最高公因数是 2 * 2 * 3 = 12

20 = 2 * 2 * 5

28 = 2 * 2 * 7

这两个数的最高公因数是 2 和 2。

所以，这两个数的最高公因数是 2 * 2 = 4。

方法 1

这个问题可以通过找到这两个数的所有质因数，然后找到公因数并返回它们的乘积来解决。

找到第一个数的因数
找到第二个数的因数
找到两个数的公因数
将它们相乘得到最大公约数

C++ 代码

#include <bits/stdc++.h>
#define MAXFACTORS 1024 // Let us consider max factors can be 1024
using namespace std;

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 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);


	// Step 2.
	FindFactorization(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;
}


int main()

{

	int m = 36, n = 60;
	cout << "GCD of " << m << " and " << n << " is "
		<< gcdMiddleSchoolProcedure(m, n);

	return (0);
}

输出

GCD of 36 and 60 is 12

方法 2

方法 1 可以使用欧几里得算法以更有效的方式解决。该算法遵循这样的思想：如果较小的数从较大的数中减去，则最大公约数不会改变。

C++ 代码

#include <iostream>
using namespace std;

int gcd(int a, int b) // The function runs recursive in nature to return GCD
{
 
    if (a == 0) // If a becomes zero
       return b; // b is the GCD 
    if (b == 0)// If b becomes zero
       return a;// a is the GCD 
  
   
    if (a == b) // The case of equal numbers 
        return a; // return any one of them 
  
   // Apply case of substraction 
    if (a > b) // if a is greater subtract b 
        return gcd(a-b, b);
    return gcd(a, b-a); //otherwise subtract a 
}
  

int main()
{
    int a = 36, b = 60;
    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
    return 0;
}

输出

GCD of 36 and 60 is 12

方法 3

方法二可以进一步优化，使用模运算符代替减法。

C++ 代码

#include <iostream>
using namespace std;

int gcd(int a, int b) // The function runs recursive in nature to return GCD
{
    if (b == 0) // if b becomes 0 return a 
        return a;
    return gcd(b, a % b); // divide to a by b to make smaller number 
     
}
  

int main()
{
    int a = 60, b = 36;
    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
    return 0;
}

输出

GCD of 60 and 36 is 12

下一主题C++ 程序求四个数中的最大值

查找两个数字的 GCD 的 C++ 程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

查找两个数字的 GCD 的 C++ 程序

相关帖子

C++ 可见性模式

C++ 抽象数据类型

C++ 中所有 1 的最大正方形子矩阵

C++ 比较字符串的不同方法

通过将两个连续的 1 转换为 0 来确定游戏获胜者（C++）

C++ 中的 deque::front() 和 deque::back()

C++ Strpbrk() 函数

C++ STRCMP()

C/C++ iswgraph()

C++ 中查找右侧较小元素的数量

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器