四种求最大公约数的算法 C / C++

这篇具有很好参考价值的文章主要介绍了四种求最大公约数的算法 C / C++。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

本篇文章总结了四种求最大公约数的常用算法。
包括:辗转相除法、穷举法(枚举法)、更相减损法、Stein算法
每个算法都附加流程图及 C/C++ 代码,并对其时间复杂度进行了分析。


一、辗转相除法

1. 算法简介

辗转相除法又称欧几里得算法,是指用于计算两个正整数a,b的最大公约数。欧几里得算法可用于RSA加密等领域。

假如:需要求 2022 和 409 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
2022 / 409 = 4 (余 386)
409 / 386 = 1(余 23)
386 / 23 = 16(余 18)
23 / 18 = 1 (余 5)
18 / 5 = 3 (余 3)
5 / 3 = 1 (余 2)
3 / 2 = 1 (余 1)
2 / 1 = 2 (余 0)
因此,最大公约数为1。
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 2022 和 409 的最大公约数 1。

2. 算法描述

假设有两个数a、b (a > b),c为a与b的余数,求a与b的最大公约数。

使用步骤:
Step 1 将两个数分别存入a、b中,并满足 a > b
Step 2 求 c = a % b
Step 3 判断 c 是否为 0
Step 4 若 c == 0 则 b 为最大公约数;若 c != 0 则重复步骤 2 ~ 4

流程图:
四种求最大公约数的算法 C / C++

3. 代码及复杂度

// 辗转相除法
int gcd(int a,int b)
{
	if(a % b == 0)
		return b;
	else
		return gcd(b ,a % b);
}

注意:调用该函数时,一定要保证 a > b

时间复杂度:O(log2n)


二、穷举法(枚举法)

1. 算法简介

将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,合适就保留,不合适就丢弃。

枚举算法要列举问题的所有可能的答案,所以它具备以下几个特点
1、得到的结果肯定是正确的;
2、可能做了很多的无用功,浪费了宝贵的时间效率低下
3、通常会涉及到求极值(如最大,最小,最重等)。
4、数据量大的话,可能会造成时间崩溃。

2. 算法描述

采用枚举算法解题的基本思路:
(1)确定枚举对象、枚举范围和判定条件;
(2)枚举可能的解,验证是否是问题的解。

对于本算法,要从两个数中较小的数开始由大到小列举找到公约数后立即中断列举,得到的公约数便是最大公约数。

流程图:
四种求最大公约数的算法 C / C++

3. 代码及复杂度

// 穷举法(枚举法)
int divisor(int a, int b) // 求两数的最大公约数的函数 返回值为最大公约数
{
    int  temp;// 定义整型变量temp 临时储存需要判断是否为最大公约数的值
    temp = (a > b) ? b : a;// 求出两个数中的最小值 赋给temp
    while (temp > 0)
    {
        if (a % temp == 0 && b % temp == 0)// 只要找到一个数能同时被a,b所整除,则中止循环
            break;
        temp--;// 如不满足if条件则变量自减,直到能被a,b所整除 
    }
    return (temp);
}

时间复杂度:O(n)


三、更相减损法

1. 算法简介

更相减损法又叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。

2. 算法描述

使用步骤:
Step 1 任意给定两个正整数;判断它们是否都是偶数。
Step 2 若是,则用2约简;若不是则执行Step 3。
Step 3 以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
Step 4 Step 2 中约掉的若干个 2 的积 与 Step 3 中等数的乘积 就是所求的最大公约数。
注:其中所说的 “等数” ,就是公约数。求 “等数” 的办法是 “更相减损法” 。

流程图:
四种求最大公约数的算法 C / C++

3. 代码及复杂度

// 更相减损法
int gcd2(int a, int b)
{
    int i = 0, temp, x;
    while (a % 2 == 0 && b % 2 == 0)// 判断m和n能被多少个2整除
    {
        a /= 2;
        b /= 2;
        i++;
    }
    if (a < b) // a保存大的值
    {
        temp = a;
        a = b;
        b = temp;
    }
    do
    {
        x = a - b;
        a = (b > x) ? b : x; // 更新大数的值
        b = (b < x) ? b : x; // 更新小数的值
        if (b == (a - b))
            break;
    }while (x);
    if (i == 0)
        return b;
    else
        return (int)pow(2, i) * b;
}

时间复杂度:O(n)


四、Stein算法(二进制算法)

1. 算法简介

Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。

Stein算法欧几里德算法的对比:
欧几里德算法每次迭代中最恶劣的情况是,a = 2b - 1,这样,迭代后,r=b-1。
如果a小于2n,这样大约需要4n次迭代。
而Stein算法,每次迭代后,显然An+1Bn+1≤ AnBn/2,最大迭代次数也不超过4n次。
也就是说,迭代次数几乎是相等的。但是,需要注意的是,对于大素数,试商法将使每次迭代都更复杂,因此对于大素数,Stein算法将更有优势。

2. 算法描述

原理:gcd(kx,ky)=k*gcd(x,y)

对两个正整数 x>y ,分为以下情况:
均为偶数 gcd(x,y)=2gcd(x/2,y/2);
均为奇数 gcd(x,y)=gcd((x+y)/2,(x-y)/2);
x奇 y偶 gcd(x,y)=gcd(x,y/2);
x偶 y奇 gcd(x,y)=gcd(x/2,y) 或 gcd(x,y)=gcd(y,x/2).

流程图:
四种求最大公约数的算法 C / C++

3. 代码及复杂度

//Stein算法
int Stein(unsigned int x, unsigned int y) // 求 x 和 y 的最大公因数
{
    int factor = 0;
    int temp;
    if (x < y) // 使两个数 x > y
    {
        temp = x;
        x = y;
        y = temp;
    }
    if (y == 0) // 排除求0的最大公因数的情况
    {
        return 0;
    }
    while (x != y)
    {
        if (x & 0x1) // x为奇数
        {
            if (y & 0x1) // x为奇数 y也为奇数
            {
                y = (x - y) >> 1;
                x -= y;
            }
            else // x为奇数 y为偶数
            {
                y >>= 1;
            }
        }
        else // x为偶数
        {
            if (y & 0x1) // x为偶数 y为奇数
            {
                x >>= 1;
                if (x < y)
                {
                    temp = x;
                    x = y;
                    y = temp;
                }
            }
            else // x为偶数 y也为偶数
            {
                x >>= 1;
                y >>= 1;
                ++factor;
            }
        }
    }
    return (x << factor);
}

时间复杂度:O(log2n)文章来源地址https://www.toymoban.com/news/detail-436957.html

到了这里,关于四种求最大公约数的算法 C / C++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言经典算法之Euclidean算法求最大公约数

    目录 前言 A.建议 B.简介 一 代码实现 二 时空复杂度 A.循环实现 a.时间复杂度(Time Complexity): b.空间复杂度(Space Complexity): B.递归实现 a.时间复杂度(Time Complexity): b.空间复杂度(Space Complexity): 三 优缺点 A.循环实现 a.优点: b.缺点: c.总结: B.递归实现 a.优点:

    2024年03月26日
    浏览(55)
  • C语言—求最大公约数(4种算法思路)

    如果大数可以整除小数,那么最大公约数为小数。如果不能整除小数,那么这两个数就按大到小依次对比小数小的数求余,遇到都能够整除的,就是最大公约数。 用a对b求余,若余数为0,则除数b为最大公约数。若余数不为0,将此余数r作为新的除数,b作为新的被除数,重新

    2024年04月13日
    浏览(39)
  • 数论 --- 约数和定理公式推导、最大公约数、欧几里得算法

    和试除法判断一个数是不是质数是一个道理 从小到大枚举所有的约数,如果当前数能整除这个数的话,说明这个数就是当前数的约数 优化,与试除法判断质数是一样的 如果 d 是 n 的约数,n / d 也一定能整除 n,一个数的约数也一定是成对出现的,在枚举的时候也可以只枚举

    2023年04月08日
    浏览(85)
  • 每天一道算法练习题--Day22&& 第一章 --算法专题 --- ----------最大公约数

    关于最大公约数有专门的研究。 而在 LeetCode 中虽然没有直接让你求解最大公约数的题目。但是却有一些间接需要你求解最大公约数的题目。 时间复杂度:最好的情况是执行一次循环体,最坏的情况是循环到 smaller 为 1,因此总的时间复杂度为 O ( N ) O(N) O ( N ) ,其中 N 为 a 和

    2024年02月03日
    浏览(54)
  • 全定制FPGA硬件电路设计实现最大公约数求取算法(Quartus II)

    目录 一、设计需求 二、设计工具及版本 三、设计原理及结构方案 四、电路设计描述 1. 32位D触发器 2. 32位多路选择器 3. 32位减法器 4. 32位求余电路 5. GCDOUT信号产生电路 6. DONE_L信号产生电路 五、仿真激励设计方案及电路仿真结构 六、设计总结 当前,FPGA设计在很多场合得到

    2024年02月20日
    浏览(49)
  • [Go版]算法通关村第十三关黄金——数字数学问题之数论问题(最大公约数、素数、埃氏筛、丑数)

    题目链接:LeetCode-1979. 找出数组的最大公约数 辗转相除法其核心部分为:若r 是a ÷ b的余数,则 gcd(a, b)=gcd(b, r) 题目链接:LeetCode-204. 计数质数 如果 x 是质数,那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数。 时间复杂度分析: 外层循环的迭代次数是 n-2,即 O ( n ) O(n) O ( n ) 次

    2024年02月11日
    浏览(39)
  • 【约数】求最大公约数——递归

    请使用递归算法计算正整数n和m的最大公约数GCD(n,m)。 G C D ( n , m ) = { = m , 当 m = n 且 n m o d m = 0 = G C D ( m , n ) , 当 n m 时 = G C D ( m , n m o d    m ) , 其他 GCD(n,m)=left{begin{matrix} =m,当 m=n 且 n mod m =0\\\\ =GCD(m,n),当nm时\\\\ =GCD(m,n mod m),其他 end{matrix}right. GC D ( n , m ) = ⎩ ⎨ ⎧ ​ = m

    2024年02月03日
    浏览(42)
  • 辗转相除法求最大公约数

    辗转相除法也被称为欧几里得算法,是求两个整数的最大公约数(GCD)的一种常用方法。 辗转相除法的原理是基于两个整数的最大公约数与它们的余数的最大公约数相等的性质。具体步骤如下: 用较大的数除以较小的数,得到一个商和余数。 如果余数为0,则较小的数即为最

    2024年02月05日
    浏览(66)
  • 最大公约数和最小公倍数问题

    等差数列 蓝桥杯192 gcd问题 题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。 现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项? 思路:求出每一项之差的最大公约数,以这个

    2023年04月09日
    浏览(41)
  • 【ARM汇编】如何用汇编求最大公约数?

    CSDN话题挑战赛第1期 活动详情地址 :话题PK赛 参赛话题 :汇编知识分享 话题描述 :我们的计算机知识就像一座金字塔,底层是数学,上面是数字电路,然后是汇编,再往上是操作系统、网络、数据库、高级编程语言、框架等等…我们不可能精通这个金子塔的每一层, 但是

    2024年01月25日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包