辗转相除法:(求最大公约数)

辗转相除法:(最大公约数)
又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。
它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。
如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

#include
void main()
{
    int gcd(int a, int b);
    int m, n;

    printf("please intput two numbers:\n");
    scanf_s("%d%d", &m, &n);
    printf("gcd(%d,%d) = %d\n", m, n, gcd(m, n));

}
int gcd(int a, int b)
{
    int r=1, t;

    if (a < b)
    {
        t = a;
        a = b;
        b = t;
    }
    while (r != 0)
    {
        r = a % b;
        if (r == 0)
        {
            return b;
            break;
        }
        else
        {
            a = b;
            b = r;
        }
    }

}

Original: https://www.cnblogs.com/iforeverhz/p/16255987.html
Author: iforeverhz
Title: 辗转相除法:(求最大公约数)

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/583246/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • Mybatis源码解读-插件

    注册 xml方式的注册,是在XMLConfigBuilder#pluginElement完成的。 不明觉厉的同学,请参考上一篇文章:Mybatis源码解读-配置加载和Mapper的…

    Linux 2023年6月7日
    062
  • 深入理解linux内核-内存寻址

    逻辑地址:由一个段和偏移量组成的地址线性地址(虚拟地址):物理地址:CPU的物理地址线相对应的地址32或36位 多处理器系统中每个CPU对应一个GDT 局部线程存储:用于线程内部的…

    Linux 2023年6月6日
    057
  • tcp 连接 time-wait 状态过多问题解释

    前言 两条竖线分别是表示: 主动关闭(active close)的一方 被动关闭(passive close)的一方 网络上类似的图有很多,但是有的细节不够,有的存在误导。有的会把…

    Linux 2023年6月16日
    0151
  • 利用Hugo与GitHub仓库搭建免费的个人博客

    软件下载 配置环境变量 检验环境变量 创建博客文件 创建站点文件夹 下载主题 新建博客 将个人博客部署到github存储仓库 保姆级 基于Win10环境下的Hugo免费博客搭建 软…

    Linux 2023年6月7日
    072
  • 访问权限控制

    一.编译单元 1-1 概念 一个Java源代码文件通常被称为一个编译单元,每个编译单元的后缀需是.java,并且每个编译单元中最多只能有1个public类(当然,可以为0个)。 1…

    Linux 2023年6月8日
    075
  • git 那些事儿 —— 基于 Learn Git Branching

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年9月10日
    0212
  • 音频属性

    采样频率就是采用一段音频,做为样本,因为wav使用的是数码信号,它是用一堆数字来描述原来的模拟信号,所以它要对原来的模拟信号进行分析,我们知道所有的声音都有其波形,数码信号就是在原…

    Linux 2023年6月8日
    076
  • Spring Session Redis

    http://www.infoq.com/cn/articles/Next-Generation-Session-Management-with-Spring-Session Or…

    Linux 2023年5月28日
    061
  • 网卡的RX Ring和TX Ring

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年10月19日
    0221
  • 安装clearos系统

    镜像下载、域名解析、时间同步请点击阿里云开源镜像站 一、clearos介绍 ClearOS是一个基于CentOS和Red Hat Enterprise Linux的简单,开源,价格…

    Linux 2023年5月27日
    063
  • 使用input+datalist简单实现实时匹配的可编辑下拉列表-并解决选定后浏览器默认只显示value的可读性问题

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年10月15日
    0248
  • Redis连接出现Error: Connection reset by peer的问题是由于使用Redis的安全模式

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年9月14日
    0267
  • [Linux]OpenSuse12图形和文字界面转换

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0271
  • Redis具体解释

    2、 redis.windows.conf各项配置參数介绍 默认情况下,redis不是在后台模式执行的,假设须要在后台进程执行。把该项的值更改为yes。默觉得no daemoniz…

    Linux 2023年5月28日
    070
  • Linux启动/停止/重启Mysql数据库的方法

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0239
  • mac使用brew安装postgresql

    在您的命令行中运行以下命令: brew doctorbrew update安装在您的命令行中运行以下命令:brew install postgres 你也可以指定版本: brew …

    Linux 2023年6月14日
    085
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球