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

运行结果

方法二:辗转相除法

辗转相除法又称欧几里得算法,是指用于计算两个非负整数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;
}

运行结果

方法三:更相减损法

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

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

白话文译文:

(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用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语言实现求最大公约数的三种方法的详细内容,更多关于C语言求最大公约数的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++求最大公约数四种方法解析

    C++求最大公约数的四种方法思路,供大家参考,具体内容如下 将最近学的求最大公约数的四种方法总结如下: 第一种:穷举法之一 解释:拿其中一个数出来,用一个临时变量(tem)保存,每次都把那两个数除以这个临时变量.如果能除断,直接返回tem:如果不能除断,tem- -,直到都能除断,再返回tem.tem就是它们的最大公约数. #include <iostream> using namespace std; int CommFactor1(int m, int n); //函数的声明 int ma

  • C++ 实现求最大公约数和最小公倍数

    C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢

  • C++求四个正整数最大公约数的方法

    本文实例讲述了C++求四个正整数最大公约数的方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 输入四个正整数,输出其最大公约数. * 问题描述: * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int f(int,int); int g(int,int,int,int); int main()

  • C语言求两个正整数的最大公约数示例代码

    目录 前言 1.穷举法 2.欧几里得算法(辗转相除法) 3.递归方法 附:相减法 总结 前言 两个正整数的最大公约数(Greatest Common Divisor, GCD)是能够整除这两个整数的最大整数.两个正整数的最大公约数的求法有多种解答,本文就三种方法做详细介绍:穷举法.欧几里得算法(辗转相除法).递归方法. 我们从一道问题来引入:编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的最大公约数. 1.穷举法 根据最大公约数的定义,我们可以采用一种最简单的方

  • C语言最大公约数示例教程

    目录 穷举法  辗转相除法  辗转相减法 穷举法 (1) i= a ,b中较小的数 (2)若a,b能同时被i整除,则i即为最大公约数,结束 (3)若不能,则 i--,再回去执行(2) #include<stdio.h> int main() { int i = 0; int j = 0; scanf("%d %d", &i, &j); int k = i > j ? i : j;//i>j,k=i;i<j,k=j while(1) { if

  • C++ 实现多数的最大公约数的实例

    C++ 实现多数的最大公约数的实例 题目:求最大公约数 输入一组正整数(数量小于20),输出其最大公约数. 输入:121 33 44 11 1111 输出:11 基本思路: 从第一个数开始,和第二个数比较找它两的最大公约数,然后找出的最大公约数和第三个数比较,依次类推... #include <stdio.h> int gcd(int a,int b) { return a%b?gcd(b,a%b):b; } int main() { int N,a[20],k,i; while(~scanf

  • 详解C语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0).根据通式写出算法不难,这里就不给出了.这里给出<编程之美>上的算法,主要是为了减少迭代的次数.      对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1).另外,如果x = p * x1,假设p为素数

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

    目录 题目描述 问题分析 代码实现 方法一:穷举法 方法二:辗转相除法 方法三:更相减损法 题目描述 求任意两个正整数的最大公约数 问题分析 最大公因数,也称最大公约数.最大公因子,指两个或多个整数共有约数中最大的一个.a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号.求最大公约数有多种方法,常见的有质因数分解法.短除法.辗转相除法.更相减损法.与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]. --百度

  • C语言实现短字符串压缩的三种方法详解

    目录 前言 一.通用算法的短字符压缩 二.短字符串压缩 (1)Smaz (2)Shoco (3)Unisox2 三.总结 前言 上一篇探索了LZ4的压缩和解压性能,以及对LZ4和ZSTD的压缩.解压性能进行了横向对比.文末的最后也给了一个彩蛋:任意长度的字符串都可以被ZSTD.LZ4之类的压缩算压缩得很好吗? 本篇我们就来一探究竟. 一.通用算法的短字符压缩 开门见山,我们使用一段比较短的文本:Narrator: It is raining today. So, Peppa and George

  • C语言求阶乘之和的三种实现方法(先阶乘再累加)

    目录 题目: 方法一:使用一层for循环实现 代码简单快捷容易理解 方法二:使用两层for循环嵌套 方法三:函数递归实现 总结 题目: 此处题目是以1-20的阶乘之和举例 方法一:使用一层for循环实现 代码简单快捷容易理解 代码示例如下: #include<stdio.h> int main() { double a = 1, sum = 0;//因为最后值可能会超出int所能接收的范围 故用double int n, i; scanf("%d", &n);//注

  • Java语言通过三种方法实现队列的示例代码

    目录 队列 图解 数组模拟队列 队列优化—循环队列 代码 使用java内部队列 代码 队列 队列是一种特殊的线性表,只允许在表的前端进行删除操作,在表的后端进行插入操作. 队列是一个有序列表,可以用数组或是链表来实现. 遵循先入先出的原则.即:先存入队列的数据,要先取出.后存入的要后取出. 就相当于我们日常生活中的排队,先来先服务,后来的只能在后面进行排队等待. 图解 数组模拟队列 通过对定义的了解,发现队列很像我们的数组,那我们是不是可以通过数组来模拟队列,下面我们来实践一下. 首先先分析一下

  • PHP编程求最大公约数与最小公倍数的方法示例

    本文实例讲述了PHP编程求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: //求最大公约数 function max_divisor($a,$b) { $n = min($a, $b); for($i=$n; $i>1; $i--) { if (is_int($a/$i)&&is_int($b/$i)) { return $i; //此处如果用echo $i;则输出结果为432:故应区分echo.return的区别 } } return 1; } //求最小公倍数 f

  • java求最大公约数与最小公倍数的方法示例

    本文实例讲述了java求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: Gongyueshu.java文件: package math; public class Gongyueshu { public static void main(String[] args) { //从控制台输入两个数据 int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); int y = 1 ; int b = 1;

  • python求绝对值的三种方法小结

    如下所示: 1.条件判断 2.内置函数abs() 3.内置模块 math.fabs abs() 与fabs()的区别 abs()是一个内置函数,而fabs()在math模块中定义的. fabs()函数只适用于float和integer类型,而abs()也适用于复数. abs()返回是float和int类型,math.fabs()返回是float类型 以上这篇python求绝对值的三种方法小结就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Go语言net包RPC远程调用三种方式http与json-rpc及tcp

    目录 一.服务端 二.http客户端 三.TCP客户端 四.json客户端 五.运行结果 rpc有多种调用方式,http.json-rpc.tcp 一.服务端 在代码中,启动了三个服务 package main import ( "log" "net" "net/http" "net/rpc" "net/rpc/jsonrpc" "sync" ) //go对RPC的支持,支持三个级别:T

  • 漫画讲解C语言中最近公共祖先的三种类型

    最近公共祖先定义 查找最近公共祖先 三叉链 代码如下: //三叉链 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode *parent; TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {} }; class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* ro

  • C语言三种方法解决轮转数组问题

    目录 题目 1.题目描述 2.要求 3.原题链接 二.相关知识点 三.解决思路 旋转法 直接法 空间换取时间 题目 1.题目描述 给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数. 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 2.要求 进阶

随机推荐