-
2020-12-24 17:56:40
1 .用辗转相除法求最大公约数
算法描述:
m对n求余传给自己,再次求余, 若余数等于0
则 n 为最大公约数
2.最小公倍数 = 两个数的积 / 最大公约数基本思想是采用将两个数相乘,然后除以它们的最大公约数 function getMinCommonMultiple(a, b){ return a * b / getMaxCommonDivisor(a, b); }
在我国古代的《九章算术》中就有记载,现摘录如下:
约分术曰:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法,实际上就是辗转相除法。
辗转相除法求最大公约数,是一种比较好的方法,比较快。
更多相关内容 -
多个数求最小公倍数详解!
2019-12-30 11:40:48有了公式,我们很清楚可以知道了,只要有最大公约数就可以求出最小公倍数,因为两数乘积肯定是已知的,所以下面将讲解一下两个数如何求最大公约数。 1.辗转相除法(方法有很多,只介绍我会的,并且易懂的h...最小公倍数
既然想算最小公倍数,首先要清楚最小公倍数的求法,还有最大公约数的求法
最小公倍数*最大公约数=两数乘积
有了公式,我们很清楚可以知道了,只要有最大公约数就可以求出最小公倍数,因为两数乘积肯定是已知的,所以下面将讲解一下两个数如何求最大公约数。
1.辗转相除法(方法有很多,只介绍我会的,并且易懂的hhhh)
辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:
用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。
好吧,定义总是那么的复杂且难懂,下面直接一张表格,实现一遍辗转相除法,聪明的你肯定一遍就看会!
15 55 15=15%55 10=55%15 5=15%10 0=10%5(最大公约数 5 )
如果你看懂了两个数如何求最小公倍数,那么求多个数的最小公倍数就不难了。
主要就是遵循一个准则:
先求前两个数的最小公倍,再用这个最小公倍数与下一个数求最小公倍数
再举一个例子求一下(5 7 15) 的最小公倍数
字迹可能
有些潦草,但是很认真哈哈哈哈哈哈!
如果大致过程会了,代码肯定是会了
代码实现:
import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n-- > 0) { int k = sc.nextInt(); int sum = 1; for (int i = 0; i < k; i++) { int p = sc.nextInt(); sum *= p / ff(sum, p); } System.out.println(sum); } } public static int ff(int x,int y){ int r ; while(y!=0){ r=x%y; x=y; y=r; } return x; } }
没有考虑大数的问题,根据题意选择long还是int。
下面介绍一个杭电oj的题目,因为你即使看的再懂不去实践也是不行的!
比如杭电的2028!
总结
大家共同学习,写错的地方请提出谢谢。
-
求两个数的最小公倍数及多个数的最小公倍数的求法
2019-02-02 21:56:47一种是最容易想到的穷举法:最小公倍数肯定大于等于两个数的最大数,因此从最大数开始,用循环语句使不断增加,当增加到某个数可与i同时整除这两个数时,该数则为这两个数的最小公倍数。 一种是使用公式a * b=gcd* ...最小公倍数的两种求法:
一种是最容易想到的穷举法:
- 先考虑特殊情况,当较大数是较小数的整数倍时,
- 两个数互质时,可直接快速得出最小公倍数。
- 一般情况:最小公倍数肯定大于等于两个数的最大数且肯定为较大数的整数倍,因此从最大数开始,用循环语句使不断增加最大数的整数倍,当增加到某个整数倍时可与同时整除这个较小数时,该较大数的整数倍数则为这两个数的最小公倍数。
一种是使用公式a * b=gcd* lcm ,两数之积等于这两个数的最小公倍数和最大公约数的
注:
- gcd和lcm代表a和b最大公约数和最小公倍数;
- 该公式仅用于计算两个数的gcd和lcm,对多个数不成立;
- 上述穷举法中的特殊情况也可由此公式验证
公式证明:假设两个数a和b,它们的最大公约数是:gcd
那么设:a=k1gcd ; b=k2gcd ;
因为gcd为a和b的最大公约数 ,故k1和k2互质,所以k1和k2的最小公倍数为k1k2;(上述穷举法中有提到)
那a和b的最小公倍数lcm=k1k2gcd=(a/gcd)(b/gcd)gcd;
可得公式lcmgcd=ab ;代码实现:
想了解求最大公倍数的算法可戳:最大公约数的三种算法#include<stdio.h> void Least_common_multiple1(int a, int b);//穷举法 void Least_common_multiple2(int a,int b);//最大公倍数法 int Greatest_common_divisor(int a, int b); void swap(int *x, int *y); int main() { int a, b; printf("请输入a,b的值:"); scanf("%d%d", &a, &b); if (a == 0 || b == 0) { printf("0没有最小公倍数!,请重新输入:"); scanf("%d%d", &a, &b); } Least_common_multiple1(a, b); Least_common_multiple2(a, b); system("pause"); return 0; } void Least_common_multiple1(int a, int b)//穷举法 { if (a<b) { swap(&a,&b); if (0 == a%b) { printf("%d\n", a);//当较大数可以整除较小数时,较大数即为这两个数的最小公倍数 } } if (1 == Greatest_common_divisor(a, b))//考虑到两个数互为质数时,最小公倍数为两个数的积(可由公式a*b=gcd*lcm;gcd=1得) { printf("%d\n", a*b); } int t = a > b ? a : b; for (int i = t;; i+=t) { if ((i%a == 0) && (i%b == 0)) { printf("%d\n", i); break; } } } void Least_common_multiple2(int a,int b) { printf("%d\n", a*b / Greatest_common_divisor(a, b)); } int Greatest_common_divisor(int a, int b) { a = abs(a); b = abs(b); if (a < b) { swap(&a, &b); } while (b) { int t = a%b; a = b; b = t; } return a; } void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
求多个数的最小公倍数
递归:
分析:先求得出前面数的最小公倍数,再不断将这个数与后面做最小公倍数运算,直至求完每一个数。
代码实现:#include<stdio.h> #define max 4 void set_array();//设置数组 void print_array();//打印数组 void swap(int *x, int *y);//交换两数的值 int Least_common_multiple(int a,int b);//求两个数的最小公倍数 int Greatest_common_divisor(int a, int b);//求两个数的最大公倍数 int main() { int array[max]; set_array(array); print_array(array); int lcm=array[0]; for (int i = 1; i < max; i++) { lcm=Least_common_multiple(lcm, array[i]); } printf("\n%d\n", lcm); return 0; } void set_array(int *p) { for (int i = 0; i < max; i++) { scanf("%d",&p[i]); } } void print_array(int *p) { for (int i = 0; i < max; i++) { printf("%d\t",p[i]); } } int Greatest_common_divisor(int a, int b) { if (a < b) { swap(&a, &b); } while (b) { int t = a%b; a = b; b = t; } return a; } void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } int Least_common_multiple(int a, int b) { return a*b / Greatest_common_divisor(a, b); }
穷举法:
分析:一组数的最小公约数肯定在这组数的最大值和这组数的乘积之间;故从最大值开始穷举,当某个数可以整除这组所有数时,即得到这组数的最小公倍数。
代码实现:#include<stdio.h> #include<stdbool.h> #define max 4 void Set_array(int *p);//设置数组 void Print_array(int *p);//打印数组 bool Determine_divisible(int *p, int lcm);//判断lcm是否可以整除p中所有数 int Max_num(int *p);//返回这组数中的最大值 int main() { int array[max]; Set_array(array); Print_array(array); int lcm = Max_num(array); for (int i = lcm;; i++) { if (Determine_divisible(array,i )) { printf("这组数的最小公倍数为:%d\n", i); break; } } for (int i = array[0];; i++) { if (Determine_divisible(array, i)) { printf("这组数的最小公倍数为:%d\n", i); break; } } return 0; } void Set_array(int *p) { for (int i = 0; i < max; i++) { scanf_s("%d", &p[i]); } } void Print_array(int *p) { for (int i = 0; i < max; i++) { printf("%d\t", p[i]); } } bool Determine_divisible(int *p,int lcm) { for (int i = 0; i < max; i++) { if (lcm%p[i]!= 0) { return false; } } return true; } int Max_num(int *p) { int t=p[0]; for (int i = 0; i < max; i++) { t = t>p[i] ? t : p[i]; } return t; }
-
数学算法:求多个数的最小公倍数
2017-03-25 10:16:302、运用小学奥数的算法,多个数的最小公倍数,先将两个数的最小公倍数求出,再与后面的数求最小公倍数。两个数的最小公倍数,可以先将两个数相乘再除两个数的最小公因数。为了避免溢出,可以先相除再相乘。题目:...解体心得:
1、一开始我的算法是找出最大的那个数,再将那个数一倍一倍的相加,但是会超时,因为题目的限制是32bits。(过于天真)
2、运用小学奥数的算法,多个数的最小公倍数,先将两个数的最小公倍数求出,再与后面的数求最小公倍数。两个数的最小公倍数,可以先将两个数相乘再除两个数的最小公因数。为了避免溢出,可以先相除再相乘。
3、有一个比较简单的求最大公因数的库函数调用(__gcd(int a,int b)),但不是标准库,头文件使用万能头文件。题目:
Problem Description The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer. Output For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer. Sample Input 2 3 5 7 15 6 4 10296 936 1287 792 1 Sample Output 105 10296 Source East Central Northmerica 2003, Practice
#include<bits/stdc++.h> using namespace std; //为了防止溢出全开long long,gcd函数是找出两个数的最大公因数(辗转相除法); long long gcd(long long a,long long k) { if(k == 0) return a; else return gcd(k,a%k); } int main() { int t; cin>>t; while(t--) { int n; cin>>n; long long k,cnt,a; a = cnt = 1; while(n--) { cin>>k;//一边输入一边计算,节省时间 cnt = a/gcd(a,k)*k;//先除后乘防止溢出; a = cnt; } cout<<cnt<<endl; } }
求最大公因数的库函数使用:
#include<bits/stdc++.h> //好像只能使用这个头文件 using namespace std; int main() { int a,b; while(scanf("%d%d",&a,&b)!=EOF) { printf("%d\n",__gcd(a,b)); //不是标准库中的函数 } }
-
java代码求n个数的最小公倍数,HDOJ 2028,3种方法实现
2021-03-09 02:07:06题目链接点击打开链接题目大意为:求n个正整数的最小公倍数解题思路:求最小公倍数的方法我们在数学中学到过,我知道的有2种方法分别是(1)求最大公约数法(2)使用辗转相除法求 比如:下图为求 2 4 6的最小公倍数,用2... -
求多个数的最小公倍数 (java+大数)
2018-05-03 20:10:112043: 最小公倍数时间限制: 1 Sec 内存限制: 64 MB提交: 11 解决: 9您该题的状态:已完成[提交][状态][讨论版]题目描述为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。但也并非纯粹的偶然:60... -
多个数的最小公倍数
2022-03-21 20:17:12题目描述 输入n个数,请计算它们的最小公倍数。如5、7、15的最小公倍数是105。 输入 首先输入一个正整数T,表示测试数据的组数,然后是T组的测试数据。 每组测试先输入一个整数n(2 -
C#获取两个数的最大公约数和最小公倍数示例
2020-12-31 15:03:38最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个。 代码如下:/// <summary>/// 最大公约数/// </summary>/// ”a”></param>/// ”b... -
Python 求多个数的最小公倍数
2019-07-24 10:21:29Python 求多个数的最小公倍数 def mcm(*num): minimum = 1 for i in num: minimum = int(i) * int(minimum) / m.gcd(int(i), int(minimum)) return int(minimum) -
C++题解:多个数的最小公倍数
2021-08-10 15:05:48求n个数的最小公倍数。 输入格式 第一行一个整数 n(2≤n≤20)。 第二行n个整数。 输出格式 一个整数,表示最小公倍数,数据保证答案不超过int范围。 输出时每行末尾的多余空格,不影响答案正确性 要求使用「... -
用python编写两个正整数的最大公约数和最小公倍数的小程序
2020-12-22 11:47:41show 程序代码 废话不多说,直接上程序片段 nummax,nummin=eval(input("请输入两个正整数,并用逗号连接:")) if (nummax % 1 !...print(str(nummax)+"和"+str(nummin)+"的最小公倍数数是: -
js实现求多个数的最小公倍数
2020-04-03 18:20:12求出前两个数出的最小公倍数与第三个数(min和arr[2])的最小公倍数,此时得到的最小公倍数就是数组前3个数的最小公倍数,以此类推。 代码如下: smallestCommons(arr) { var minCom = arr[0] // 当前最小公倍数 ... -
【C语言】求最小公倍数三种方法
2022-04-15 18:48:49求两个整数的最小公倍数的三种方法,写的不好,还请指出。 -
求多个数的最小公倍数
2018-12-22 14:01:00pid=2 参考:... main那里一直过不了,不知道为啥,然后就去搜了这个。即先求两个数的最小公倍数,再将这个数和后一个数求。 参考中求最大公约数用了递归的... -
1171 多个数的最小公倍数
2022-02-07 12:28:29也许你已经会了求2个数字最小公倍数的方法,但是如果求多个数字的最小公倍数,你又能找到办法吗? 输入要求 首先输入一个整数n表示有n个数,然后输入这n个整数。(n<=100) 输出要求 求出n个整数的最小公... -
Python求任意多个数的最小公倍数和最大公因数
2020-06-10 15:34:29def Common_multiple(number1, number2): # 求两个数的最小公倍数 while number1 % number2 !...def Maximum_common_divisor(*number): # 求任意多个数的最小公倍数 while len(number) > 1: numbe... -
c语言求最小公倍数_最小公倍数
2020-11-21 14:01:47设a1,a2,…,an是n个整数(n≥2,n∈N+),它们的公倍数有无穷多个,其中最小的正的公倍数m,称为a1,a2,…,an的最小公倍数。最小公倍数通常用方括号表示,记为m=[a1,a2,…,an].最小公倍数有以下性质:①a1,a2... -
求n个数的最小公倍数(C语言)
2021-02-05 10:20:13求n个数的最小公倍数。 Input 输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数。 Output 为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行。你可以假设最后的输出是一个32位... -
求多个数的最大公约数,最小公倍数以及hanks博士问题
2019-03-22 18:41:38求多个数的最大公约数,最小公倍数以及hanks博士son问题,数论问题 -
编程求n个数的最小公倍数
2020-04-27 14:54:35文章目录1 最大公约数、最小公倍数2 编程求两数的最大公约数、最小公倍数2.1 欧几里德算法(辗转相除法)2.2 代码实现3 编程求n个连续数字的最小公倍数 1 最大公约数、最小公倍数 最小公倍数(Least Common ... -
JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象,回归迭代和循环】
2020-12-08 22:40:38方法来自求多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来。最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) ... -
递归算法求两个数的最小公倍数 - 左耳的博客
2021-03-17 13:24:53递归算法求两个数的最小公倍数 (明明可以不用递归 你偏要递归)#includeint divide(int num1, int num2);int main(){int x=15,y=7;int c=0;c=x*y/divide(x,y);printf("%d\n",c);return 0;}int divide(int num1, int ... -
C语言求n个数的最小公倍数
2020-03-18 12:59:19这是在刷杭州电子科技大学OJ... 从1开始逐一对每个数进行除余操作,仅当每个余数都为0时才能作为公倍数,因为是从1开始即从小到大开始,所以第一个输出的公倍数就是最小公倍数,输出后跳出循环 用例:2 4 6, 表示... -
PHP实现求最大公约数与最小公倍数的方法
2021-03-23 13:47:57这篇文章主要介绍了PHP编程求最大公约数与最小公倍数的方法,涉及php数学计算的相关运算技巧,需要的朋友可以参考下具体如下://求最大公约数function max_pisor($a,$b){$n = min($a, $b);for($i=$n; $i>1; $i--){... -
python 求最小公倍数/最大公约数(2个数或者多个数的)
2020-11-06 11:12:482.最小公倍数/最大公约数 Type one: 2个数 """ 最大公约数 Author:Anderson Time:2020-11-4 """ def gcd(a,b): if a<b: a,b=b,a if a%b==0: return b else: return gcd(b,a%b) 思路分析:求两个数的最大... -
n个数的最小公倍数
2017-10-29 18:23:58求n个数的最小公倍数 【输入描述】 第一行一个数n(n 下面n个数,integer范围内 【输出描述】 这n个数的最小公倍数 【样例输入】 5 6 3 5 4 2 【样例输出】 60 【数据范围及提示】 求出最大... -
求N个数的最大公约数和最小公倍数以及Hankson"逆问题"(python)
2019-03-21 20:33:49求N个数的最大公约数和最小公倍数以及Hankson"逆问题"(python) 一、题目要求 1.基本要求: 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题 2.提高要求: 已知正整数a0,a1,b0,b1,... -
B.求多个数的最小公倍数
2022-01-13 21:43:38求多个数的最小公倍数 -
求n个数的最小公倍数(c/c++)
2022-02-07 12:30:56也许你已经会了求2个数字最小公倍数的方法,但是如果求多个数字的最小公倍数,你又能找到办法吗? 输入要求 首先输入一个整数n表示有n个数,然后输入这n个整数。(n<=100) 输出要求 求出n个整数的最小公...