详解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为素数，并且y % p != 0，那么f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。

参考代码：

//函数功能: 求最大公约数
//函数参数: x,y为两个数
//返回值:  最大公约数
int gcd_solution1(int x, int y)
{
  if(y == 0)
    return x;
  else if(x < y)
    return gcd_solution1(y, x);
  else
  {
    if(x&1) //x是奇数
    {
      if(y&1) //y是奇数
        return gcd_solution1(y, x-y);
      else  //y是偶数
        return gcd_solution1(x, y>>1);
    }
    else //x是偶数
    {
      if(y&1) //y是奇数
        return gcd_solution1(x>>1, y);
      else  //y是偶数
        return gcd_solution1(x>>1, y>>1) << 1;
    }
  }
}

求最小公倍数：
最常用的是辗转相除法，有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①

下面非递归版本：

int gcd_solution2(int x, int y)
{
  int result = 1;
  while(y)
  {
    int t = x;
    if(x&1)
    {
      if(y&1)
      {
        x = y;
        y = t % y;
      }
      else
        y >>= 1;
    }
    else
    {
      if(y&1)
        x >>= 1;
      else
      {
        x >>= 1;
        y >>= 1;
        result <<= 1;
      }
    }
  }
  return result * x;
}
赞 (0)

相关推荐

  • 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; } 感谢阅读,希望能帮助到大家,谢

  • Java求两个正整数的最大公约数和最小公倍数

    题目:输入两个正整数m和n,求其最大公约数和最小公倍数. 程序分析:利用辗除法. 最大公约数: public class CommonDivisor{ public static void main(String args[]) { commonDivisor(24,32); } static int commonDivisor(int M, int N) { if(N<0||M<0) { System.out.println("ERROR!"); return -1; }

  • C#获取两个数的最大公约数和最小公倍数示例

    最大公约数:指两个或多个整数共有约束中最大的一个. 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个. 复制代码 代码如下: /// <summary>/// 最大公约数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// &

  • 递归法求最大公约数和最小公倍数的实现代码

    数学原理:        设有两个数num1和num2,假设num1比较大.令余数r = num1 % num2.       当r == 0时,即num1可以被num2整除,显然num2就是这两个数的最大公约数.       当r != 0时,令num1 = num2(除数变被除数),num2 = r(余数变除数),再做 r = num1 % num2.递归,直到r == 0.       以上数学原理可以用具体的两个数做一下分析,这样容易理解.代码实现(求最大公约数): 复制代码 代码如下:

  • 详解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语言 如何求两整数的最大公约数与最小公倍数

    目录 题目 思路 代码 法一 法二(局部变量) 法三(全局变量) 运行结果 题目 用一函数求最大公约数,用另一函数调用此函数求出最大公约数,并用求出的最大公约数求最小公倍数. 具体要求如下: ①用全局变量.将最大公约数与最小公倍数设为全局变量,在主函数中输出它们的值. ②不用全局变量.最大公约数和最小公倍数由被调模块返回值. 思路 从两个数中选一个数,从这个数开始,逐步减一,当能够同时被两个数整除时,结束循环,即为最大公约数. 最小公倍数*最大公约数=两个数乘积. 代码 法一 #include<

  • C语言辗转相除法求2个数的最小公约数

    辗转相除法最大的用途就是用来求两个数的最大公约数. 用(a,b)来表示a和b的最大公约数. 有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c). (证明过程请参考其它资料) 例:求 15750 与27216的最大公约数. 解: ∵27216=15750×1+11466 ∴(15750,27216)=(15750,11466) ∵15750=11466×1+4284  ∴(15750,11466)=(11466,4284) ∵11466=4284×2+2898  ∴(114

  • Python自定义函数实现求两个数最大公约数、最小公倍数示例

    Python自定义函数实现求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python自定义函数实现求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 1. 求最小公倍数的算法: 最小公倍数  =  两个整数的乘积 /  最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: ① 整数A对整数B进行取整, 余数用整数C来表示    举例: C = A % B ② 如果C等于0,则C就是整数A和整数B的最大公约数 ③ 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2

  • 详解C语言读取文件求某一列的平均值

    详解C语言读取文件求某一列的平均值

    目录 第一部分:比较读取文件的效率 第二部分:比较求取列平均值的效率 第一部分:比较读取文件的效率 在之前的文章<生信(五)awk求取某一列的平均值>中,笔者曾经给出过C语言求取某列平均值的代码,但是最近回顾时发现,这段代码至少有几点不足: 1. 利用 fgetc 函数来读取文件,现在看来效率不高. 2. 如果文件最后没有一个空白行的话,会陷入无限循环.也就是对 EOF 的处理不完善. 大家都知道,C语言读取文件的常用函数有 fgetc.fgets.fread 以及 fscanf 等.笔者曾经

  • 详解R语言中的表达式、数学公式、特殊符号

    详解R语言中的表达式、数学公式、特殊符号

      在R语言的绘图函数中,如果文本参数是合法的R语言表达式,那么这个表达式就被用Tex类似的规则进行文本格式化. y <- function(x) (exp(-(x^2)/2))/sqrt(2*pi) plot(y, -5, 5, main = expression(f(x) == frac(1,sqrt(2*pi))*e^(-frac(x^2,2))), lwd = 3, col = "blue") library(ggplot2) x <- seq(0, 2*pi, b

  • 详解C语言#define预处理宏定义

    目录 #define介绍: #define宏定义无参的一般形式为:#define  标识符 常量 #define宏定义有参的一般形式为:#define  标识符(参数表) 表达式 #运算符: ##运算符: 可变宏...和__VA_ARGS__: 开发项目中常用的宏定义: #define介绍: C语言里可以用#define定义一个标识符来表示一个常量.特点是:定义的标识符不占内存,只是一个临时的符号,预编译后这个符号就不存在了,也不做类型定义.预编译又叫预处理.预编译就是编译前的处理.这个操作是在

  • 详解C语言数组越界及其避免方法

    详解C语言数组越界及其避免方法

    所谓的数组越界,简单地讲就是指数组下标变量的取值超过了初始定义时的大小,导致对数组元素的访问出现在数组的范围之外,这类错误也是 C 语言程序中最常见的错误之一. 在 C 语言中,数组必须是静态的.换而言之,数组的大小必须在程序运行前就确定下来.由于 C 语言并不具有类似 Java 等语言中现有的静态分析工具的功能,可以对程序中数组下标取值范围进行严格检查,一旦发现数组上溢或下溢,都会因抛出异常而终止程序.也就是说,C 语言并不检验数组边界,数组的两端都有可能越界,从而使其他变量的数据甚至程序代码

  • 详解Go语言运用广度优先搜索走迷宫

    详解Go语言运用广度优先搜索走迷宫

    目录 一.理解广度优先算法 1.1.分析如何进行广度优先探索 1.2.我们来总结一下 1.3.代码分析 二.代码实现广度优先算法走迷宫 一.理解广度优先算法 我们要实现的是广度优先算法走迷宫 比如,我们有一个下面这样的迷宫 这个迷宫是6行5列 其中0代表可以走的路, 1代表一堵墙. 我们把墙标上言责, 就如右图所示. 其中(0,0)是起点, (6, 5)是终点. 我们要做的是, 从起点走到终点最近的路径. 这个例子是抛转隐喻, 介绍广度优先算法, 广度优先算法的应用很广泛, 所以, 先来看看规律

随机推荐