C#获取两个数的最大公约数和最小公倍数示例
最大公约数:指两个或多个整数共有约束中最大的一个。
最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个。
/// <summary>
/// 最大公约数
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static int GCD(int a, int b)
{
int gcd = 1;
int min = a > b ? b : a;
for (int i = min; i >= 1; i--)
{
if (a % i == 0 && b % i == 0)
{
gcd = i;
break;
}
}
return gcd;
}
/// <summary>
/// 最小公倍数
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static int LCM(int a, int b)
{
int lcm = a * b;
int max = a > b ? a : b;
for (int i = max, len = a * b; i <= len; i++)
{
if (i % a == 0 && i % b == 0)
{
lcm = i;
break;
}
}
return lcm;
}
相关推荐
-
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; }
-
递归法求最大公约数和最小公倍数的实现代码
数学原理: 设有两个数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++ 实现求最大公约数和最小公倍数
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; } 感谢阅读,希望能帮助到大家,谢
-
C#获取两个数的最大公约数和最小公倍数示例
最大公约数:指两个或多个整数共有约束中最大的一个. 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个. 复制代码 代码如下: /// <summary>/// 最大公约数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// &
-
Python自定义函数实现求两个数最大公约数、最小公倍数示例
本文实例讲述了Python自定义函数实现求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 1. 求最小公倍数的算法: 最小公倍数 = 两个整数的乘积 / 最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: ① 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B ② 如果C等于0,则C就是整数A和整数B的最大公约数 ③ 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2
-
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,
-
C语言 如何求两整数的最大公约数与最小公倍数
目录 题目 思路 代码 法一 法二(局部变量) 法三(全局变量) 运行结果 题目 用一函数求最大公约数,用另一函数调用此函数求出最大公约数,并用求出的最大公约数求最小公倍数. 具体要求如下: ①用全局变量.将最大公约数与最小公倍数设为全局变量,在主函数中输出它们的值. ②不用全局变量.最大公约数和最小公倍数由被调模块返回值. 思路 从两个数中选一个数,从这个数开始,逐步减一,当能够同时被两个数整除时,结束循环,即为最大公约数. 最小公倍数*最大公约数=两个数乘积. 代码 法一 #include<
-
JavaScript实现获取两个排序数组的中位数算法示例
本文实例讲述了JavaScript实现获取两个排序数组的中位数算法.分享给大家供大家参考,具体如下: 题目 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 . 请找出这两个有序数组的中位数.要求算法的时间复杂度为 O(log (m+n)) . 你可以假设 nums1 和 nums2 不同时为空. 示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/
-
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的函数递归最大栈空间是1000(如果我没有记错的话),如果数字大一些,很容易出现爆栈. 所以在这里有两种处理方法: 1.如果较大的自然数除较小的一个自然数,取得余数,较小的自然数和余数的最大公约
-
Java求解两个非负整数最大公约数算法【循环法与递归法】
本文实例讲述了Java求解两个非负整数最大公约数算法.分享给大家供大家参考,具体如下: 代码功能: 1.Java实现(完整源码附测试用例): 2.求解两个非负整数p,q(p>=q)的最大公约数: 3.循环法 以及 递归法两种求解思路: 完整源码: /* GCD:Greateast Common Divisor */ public class GCD{ public static void main(String args[]){ /* Test Case */ int p = 32; int q
-
Python实现利用最大公约数求三个正整数的最小公倍数示例
本文实例讲述了Python实现利用最大公约数求三个正整数的最小公倍数.分享给大家供大家参考,具体如下: 在求解两个数的小公倍数的方法时,假设两个正整数分别为a.b的最小公倍数为d,最大公约数为c.存在这样的关系d=a*b/c.通过这个关系式,我们可以快速的求出三个正整数的最小公倍数. def divisor(a,b): c = a%b while c>0: a=b b=c c=a%b return b x1 = input("input1:") x2 = input("
随机推荐
- 深入解析JavaScript中的立即执行函数
- CI(CodeIgniter)简单统计访问人数实现方法 原创
- 查看物理内存的批处理
- JavaScript必知必会(三) String .的方法来自何方
- javascript实现延时显示提示框特效代码
- JavaScript动态插入script的基本思路及实现函数
- 算法系列15天速成——第十三天 树操作【下】
- Asp下实现多表单域无组件文件上传的实例
- 集群配置中IP端口转发
- 微信小程序 实现拖拽事件监听实例详解
- Python字符串格式化的方法(两种)
- 深究从MongoDB的ObjectId中获取时间信息
- canvas实现动态小球重叠效果
- Java中的集合框架
- MongoDB中ObjectId的误区及引起的一系列问题
- RecyclerView底部分割线去除的方法
- JavaScript中模拟实现jsonp
- c# 给button添加不规则的图片以及用pictureBox替代button响应点击事件的方法
- android判断动画已结束示例代码
- Yii2 中实现单点登录的方法