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

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

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

    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++ 实现多数的最大公约数的实例

    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

  • 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

  • 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求最大公约数与最小公倍数的方法示例

    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求最大公约数和最小公倍数的简单方法

    python怎么求最大公约数和最小公倍数 一.求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数.比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数. 具体代码如下: def gongyue(a, b): """ 欧几里得算法----辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 "

  • python辗转相除法求最大公约数和最小公倍数的实现

    python辗转相除法求最大公约数和最小公倍数的实现

    目录 辗转相除法求最大公约数和最小公倍数 辗转相除法数学原理 python代码实现 用递归的方式实现 Python3 20.辗转相除法 算法分析 源代码 结果截图 辗转相除法求最大公约数和最小公倍数 辗转相除法数学原理 辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法.接下来我们用实例来解释一下.假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的: 21 / 12 = 1 (余 9) 12 / 9 = 1(余 3) 9 / 3 = 3 (余 0) 至此,得到21与12

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

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

  • JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】

    本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法.分享给大家供大家参考,具体如下: 方法来自求多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来.最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) aj以外的所有其他非0项ak用ak mod aj代替:若没有除aj以外的其他非0项,则转到(4) (3) 转到(1) (4) a1,a2,..,an的最大公约数为aj 写

  • 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语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 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为素数

  • Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python基于递归和非递归算法求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了所以就写下来作为记录,也希望帮到别人,下面是代码: #!/usr/bin/env python #coding:utf-8 from fractions import gcd #非递归实现 def gcd_test_one(a, b): if a!=0 and b!=0: if a>b: a,

随机推荐