C语言求最大公约数的三种不同实现方法

小辉_Super 2024-08-06 18:29:24编程技术
155

在计算机科学与数学中,求解两个或多个整数的最大公约数(Greatest Common Divisor, GCD)是一个经典问题。最大公约数是指能够整除给定整数集合中所有整数的最大正整数。这个问题不仅具有理论意义,还在诸如密码学、数据压缩等领域有着广泛的应用。本文将介绍并展示如何使用C语言实现求解最大公约数的三种不同方法:辗转相除法、更相减损法以及穷举法。通过这些实现,读者可以加深对不同算法的理解,并掌握在实际编程中如何灵活运用它们。

题目描述

求任意两个正整数的最大公约数

问题分析

最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。

——百度百科

最大公因数的求法有不少,本文我将采用穷举法、辗转相除法、更相减损法三种方法,求两个正整数的最大公约数(最大公因数)。

代码实现

方法一:穷举法

穷举法(列举法),是最简单最直观的一种方法。

具体步骤为:先求出两个数的最小值min(最大公约数一定小于等于两个数的最小值),接着从最小值min递减遍历(循环结束条件为i > 0),如果遇到一个数同时为这两个整数的因数,则使用break退出遍历(退出循环),这时的遍历值i即为两个正整数的最大公约数。

#include <stdio.h>

/**
 * @brief 获取两个正整数的最大公因数(穷举法)
 * @param num1  第一个正整数
 * @param num2  第二个正整数
 * @return      最大公因数
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    int i = 0;
    //获取两个整数的最小值
    int min = num1 < num2 ? num1 : num2;

    //从两个数的最小值开始递减遍历
    for(i = min; i > 0; i--)
    {
        //i为num1和num2的公倍数
        if(num1 % i == 0 && num2 % i == 0)
            break;
    }
    return i;
}

int main()
{
    int num1 = 0, num2 = 0;
    puts("请输入两个正整数.");
    scanf("%d%d", &num1, &num2);
    printf("最大公约数为%d.\n", Get_Max_Comm_Divisor(num1, num2));
    return 0;
}

运行结果

C语言求最大公约数的三种不同实现方法

方法二:辗转相除法

辗转相除法又称欧几里得算法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

.欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

扩展欧几里得算法可用于RSA加密等领域。

举例:

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法,是这样进行的:

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此,最大公约数为1

以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。

——百度百科

数学学渣的我觉得这个小算法特别神奇,但我并不想深入研究(为什么能用辗转相除求最大公因数呢),假如你想证明,可以自己试着简单地证明一下,我就直接选择强记了,嘿嘿。

虽然算法不好理解,但实现过程并不算难,按照辗转相除的概念,转换成代码即可。

具体步骤:先求出两个数num1和num2的余数remainder。然后将num2赋值给num1,让上次取余时的除数num2作为下次取余时的被除数。同时将当前的余数remainder作为下次取余的除数。这样一直地辗转相除,直到余数为0,这时的除数num2就是我们要求的最大公因数。

一开始两个数不需要区分大小,因为如果num1比num2小,那么取余的结果还是num1,这样下次取余就变成了num2 % num1,即大的值在左边,作为被除数)

#include <stdio.h>

/**
 * @brief 获取两个正整数的最大公因数(辗转相除法)
 * @param num1  第一个正整数
 * @param num2  第二个正整数
 * @return      最大公因数
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    int remainder = num1 % num2;  //余数

    while(remainder != 0)
    {
        num1 = num2;      //更新被除数
        num2 = remainder; //更新除数
        remainder = num1 % num2; //更新余数
    }
    return num2;  //最后的除数即为最大公因数
}

int main()
{
    int num1 = 0, num2 = 0;
    puts("请输入两个正整数.");
    scanf("%d%d", &num1, &num2);
    printf("最大公约数为%d.\n", Get_Max_Comm_Divisor(num1, num2));
    return 0;
}

运行结果

C语言求最大公约数的三种不同实现方法

方法三:更相减损法

《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,原文是:

可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

白话文译文:

(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。

——百度百科

还有一种叫辗转相减的方法,好像和更相减损法相同,至少原理是一样的。

辗转相减法(求最大公约数),即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。例如 :两个自然数35和14,用大数减去小数,(35,14)->(21,14)->(7,14),此时,7小于14,要做一次交换,把14作为被减数,即(14,7)->(7,7),再做一次相减,结果为0,这样也就求出了最大公约数7。

——百度百科

刚才的辗转相除已经让我很吃惊了,没想到相减的方法。不过还是老规矩,直接用代码去实现这个方法,而不去证明。

不同于辗转相除法,更相减损法是需要考虑两个数的大小的,只能用大的数作为被减数,小的作为减数。

实现步骤:首先求出两个正整数num1和num2的差值diff,然后将num2赋值给num1,让上次相减时的减数num2作为下次相减时的被减数。同时将当前的差值diff作为下次相减的减数。这样一直地辗转相减,直到差值为0,这时的除数num2就是我们要求的最大公因数。

#include <stdio.h>

/**
 * @brief 获取两个正整数的最大公因数(更相减损法)
 * @param num1  第一个正整数
 * @param num2  第二个正整数
 * @return      最大公因数
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    //两数相减的结果(取正值)
    int diff = num1 > num2 ? num1 - num2 : num2 - num1;

    while(diff != 0)
    {
        num1 = num2;   //更新被减数
        num2 = diff; //更新减数
        diff = num1 > num2 ? num1 - num2\
               : num2 - num1; //更新两数相减的结果(取正值)
    }
    return num2;  //最后的减数即为最大公因数
}

int main()
{
    int num1 = 0, num2 = 0;
    puts("请输入两个正整数.");
    scanf("%d%d", &num1, &num2);
    printf("最大公约数为%d.\n", Get_Max_Comm_Divisor(num1, num2));
    return 0;
}

运行结果

C语言求最大公约数的三种不同实现方法

至于哪种方法效率更高,感兴趣的朋友可以去算算,我只知道穷举是效率最低的。

工具推荐

在线最大公约数计算器:https://www.zhanid.com/tool/gongyueshu.html

总结

本文详细介绍了如何使用C语言实现最大公约数的计算,涵盖了三种不同的方法:辗转相除法、更相减损法和穷举法。每种方法都有其独特的思路和应用场景。通过这些代码示例,我们不仅展示了算法的具体实现细节,还帮助读者理解了每种方法背后的数学原理。无论是初学者还是有经验的程序员,都可以从中获得有价值的见解,并将这些知识应用到实际问题解决中。希望本文能够为您的学习和工作提供有益的帮助。

C语言 最大公约数
THE END
ZhanShen
把烦恼扔进夕阳里,和星星一起沉沦。

相关推荐

C语言实现MD5加密的实例代码分享
MD5(Message-Digest Algorithm 5)是一种广泛使用的哈希算法,常用于数据校验和密码存储等场景。尽管MD5在安全性方面存在一些局限性,但在某些特定的应用场景中,它仍然是一个...
2024-11-20 编程技术
110

C语言进阶:深度解析 while 循环语句的用法奥秘
在 C 语言中,while 循环语句是一种重要的循环结构,它允许程序员在满足特定条件时重复执行一段代码。深入理解 while 循环语句的工作原理和应用场景对于提高 C 语言编程能力至...
2024-09-29 编程技术
196

C语言实现字母大小写转换的方法及示例代码
在计算机编程中,字符处理是一个常见的任务。特别是在文本处理应用中,字母的大小写转换是非常基础且必要的功能。C语言作为一种广泛使用的编程语言,提供了多种方法来实现字母...
2024-08-30 编程技术
124

C++首度超越C语言,荣登TIOBE编程语言排行榜亚军宝座
2024年6月,全球编程语言社区迎来了一个历史性时刻。根据TIOBE编程社区指数的最新数据,C++语言在受欢迎程度上首次超越了C语言,以10.03%的占比位居排行榜第二,而C语言则以9...
2024-06-11 新闻资讯
91

C语言实现十进制转任意进制的代码详解
这篇文章主要介绍了C语言实现十进制转任意进制,运用一个数组,通过数字每次取任意进制模,存在数组中, 再通过倒取数组中的数值,来实现进制转换,如果遇到十六进制,利用ASCII码值...
2024-05-31 编程技术
61

几款适合C语言编程软件归总
C语言编程软件适于编写系统软件,是学习编程的同学们的必备软件。c语言一种应用非常广泛的编程语言,不仅仅是在软件开发上,而且各类科研都会用到c语言。今天小编给大家汇总下...
2023-11-03 新闻资讯
56