【辗转相除法简析】 +【C语言代码运用】

本文阅读 2 分钟
首页 代码,C/C#/C++ 正文

     辗转相除法, 又名欧几里得算法(Euclidean algorithm),目的是求出两个正整数的最大公约数。 它是已知最古老的算法, 其可追溯至公元前300年前。 这条算法基于一个定理: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。 比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。

        img

   它的具体做法是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。这个和更相减损术有着异曲同工之处。

        接下来是 --> C语言程序中运用辗转相除法去求两个数的最大公约数的代码:

//两个数最大公约数
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    //求a和b的较小值
    int min = a < b ? a : b;
    int m = 0;

    //for (m = min; m > 0; m++)           //另一种方法
    //{
    //    if (a % m == 0 && b % m == 0)
    //    {
    //        break;
    //    }
    //}

    //辗转相除法  -->  效率更高
    while (a % b)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    printf("%d", b);
    return 0;
}

希望这篇文章能够对大家有所帮助img

 最后 --->  觉得好的话请点个赞呗imgimg

 

 

 

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://blog.csdn.net/forever_bryant/article/details/119947808
-- 展开阅读全文 --
KillDefender 的 Beacon 对象文件 PoC 实现
« 上一篇 02-09
Web安全—逻辑越权漏洞(BAC)
下一篇 » 03-13

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复