精华内容
下载资源
问答
  • 本文实例讲述了Python自定义函数实现求两个数最大公约数、最小公倍数。分享给大家供大家参考,具体如下: 1. 最小公倍数的算法: 最小公倍数 = 两个整数的乘积 / 最大公约数 所以我们首先要求出两个整数的最大公...
  • 本文实例讲述了Python基于递归和非递归算法求两个数最大公约数、最小公倍数。分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了...
  • C语言 | 求两个数最大公约数的四种算法

    千次阅读 多人点赞 2020-10-20 20:58:28
    如果不能整除小数,那么这两个数就按大到小依次对比小数小的数求余,遇到都能够整除的,就是最大公约数。 #include<stdio.h> #include<windows.h> #pragma warning(disable:4996) int

    给定两个数,求这两个数的最大公约数

    最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。求解的方式比较多,暴力穷举、辗转相除法、更相减损法、Stein算法
    1.暴力穷举法
    如果大数可以整除小数,那么最大公约数为小数。如果不能整除小数,那么这两个数就按大到小依次对比小数小的数求余,遇到都能够整除的,就是最大公约数。

    #include<stdio.h>
    #include<windows.h>
    #pragma warning(disable:4996)
    int main(){
    	//暴力穷举法
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf("%d%d", &a, &b);
    	if (a >= b){
    		int i = 0;
    		for (i = b; i >= 1; i--){
    			if (a%i == 0 && b%i == 0){
    				printf("最大公约数为:%d\n", i);
    				break;
    			}
    		}
    	}
    	else{
    		int j = 0;
    		for (j = a; j >= 1; j--){
    			if (a%j == 0 && b%j == 0){
    				printf("最大公约数为:%d\n", j);
    				break;
    			}
    		}
    	}
    	system("pause");
    	return 0;
    }
    

    2.辗转相除法
    用大数对小数求余,若余数为0,则除数为最大公约数。若余数不为0,将此余数作为除数,小数作为被除数,重新求余,直到余数为0为止。此时的最大公约数为余数。

    #include<stdio.h>
    #include<windows.h>
    #pragma warning(disable:4996)
    int main(){
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf("%d%d", &a, &b);
    	if (a >= b){
    		int c = a%b;
    		while (c != 0){
    			a = b;
    			b = c;
    			c = a%b;
    		}
    		printf("最大公约数为:%d\n",b);
    	}
    	else{
    		int d = b%a;
    		while (d != 0){
    			b = a;
    			a = d;
    			d = b%a;
    		}
    		printf("最大公约数为:%d\n", a);
    	}
    	system("pause");
    	return 0;
    }
    

    3.更相减损法
    当两个数相等时,最大公约数为他们其中任意一个;当两个数不相等时,用大数减小数得到的差和之前的那个小数再次相减,直到两个数相等,相等的两个中,任意一个都是最大公约数。

    #include<stdio.h>
    #include<windows.h>
    #pragma warning(disable:4996)
    int main(){
    	//更相减损法
    	int a = 0;
    	int b = 0;
    	printf("请输出两个整数:");
    	scanf("%d%d", &a, &b);
    	while ((a - b)!=0){
    		if (a > b){
    			a = a - b;
    		}
    		else{
    			b = b - a;
    		}
    	}
    	printf("最大公约数为:%d\n", b);
    	system("pause");
    	return 0;
    }
    

    4.Stein算法
    步骤:
    step1:两数均为偶数时将其同时除以2至至少一数为奇数为止,记录除掉的所有公因数2的乘积k;
    step2:如果仍有一数为偶数,连续除以2直至该数为奇数为止;
    step3:用更相减损法(辗转相减法),即GCD(a,b)=GCD(a-b,b),或辗转相除法求出两奇数的最大公约数d;
    step4:原来两数的最大公约数即为d*k。

    #include<stdio.h>
    #include<windows.h>
    #pragma warning(disable:4996)
    int main(){
    	//Stein算法
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf("%d%d", &a, &b);
    	int gcd = 0;
    	int k = 1;
    	while ((!(a & 1)) && (!(b & 1))){       //step1;
    		k <<= 1;                            //用k记录全部公因子2的乘积 ;
    		a >>= 1;
    		b >>= 1;
    	}
    	while (!(a & 1))a >>= 1;                //step2;
    	while (!(b & 1))b >>= 1;
    	if (a<b) a ^= b, b ^= a, a ^= b;        //交换,使a为较大数; 
    	while (a != b){                         //step3;
    		a -= b;
    		if (a<b) a ^= b, b ^= a, a ^= b;
    	}
    	gcd = k*a;
    	printf("最大公约数为:%d\n", gcd);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 用 Java实现 输入两个数 求两个数最大公约数,如何使用java语言求两个数最大公约数
  • 用java写的小程序,输入两个数,求得他们的最大公约数和最小公倍数
  • 如何求两个数最大公约数

    千次阅读 2020-12-20 22:00:47
    求两个数最大公约数,可以用四种方法,分别是暴力穷举法(不适用于大数字)、辗转相除法(线性代数)、更相减损法(九章算术)、stein算法(Stein算法跟更相减损术很像,而且只有比较、移位、减法,非常适合用FPGA...

    一、程序描述
    求两个数最大公约数,可以用四种方法,分别是暴力穷举法(不适用于大数字)、辗转相除法(线性代数)、更相减损法(九章算术)、stein算法(Stein算法跟更相减损术很像,而且只有比较、移位、减法,非常适合用FPGA实现。)
    二、程序要点
    1、暴力穷举法,由于是求最大公约数,所以从大到小求较为适用。利用system()函数清楚屏幕。

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include<stdlib.h>
    int main() 
    {
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf_s("%d%d", &a, &b);
    	//vs更安全的函数
    	if (a >= b) 
    	//谁小穷举到谁为止,从大到小试
    	{
    		int i = 0;
    		for (i = b; i >= 1; i--) 
    		{
    			if (a % i == 0 && b % i == 0) 
    			{
    				system("cls");
    				printf("这两个数的最大公约数为:%d\n", i);
    				break;
    			}
    		}
    	}
    	else 
    	{
    		int j = 0;
    		for (j = a; j >= 1; j--) 
    		//谁小穷举到谁,从大到小试
    		{
    			if (a % j == 0 && b % j == 0) 
    			{
    				system("cls");
    				printf("这两个数最大公约数为:%d\n", j);
    				break;
    			}
    		}
    	}
    	system("pause");
    	return 0;
    }
    

    2、辗转相除法
    线性代数方法,用大数对小数求余,若余数为0,则除数为最大公约数。若余数不为0,将此余数作为除数,小数作为被除数,重新求余,直到余数为0为止。此时的最大公约数为余数。这个方法比暴力穷举法效率高很多。

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include<stdlib.h>
    int main() 
    {
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf_s("%d%d", &a, &b);
    	if (a >= b) 
    	{
    		int c = a % b;
    		while (c != 0) 
    		{
    			a = b;
    			b = c;
    			c = a % b;
    		}
    		system("cls");
    		printf("最大公约数为:%d\n", b);//辗转相除法余数为0前一个数,余数和这个数辗转相处
    	}
    	else 
    	{
    		int d = b % a;
    		while (d != 0) 
    		{
    			b = a;
    			a = d;
    			d = b % a;
    		}
    		system("cls");
    		printf("最大公约数为:%d\n", a);//辗转相除法余数为0前一个数,余数和这个数辗转相处
    	}
    	system("pause");
    	return 0;
    }
    

    3、更相减损法
    两个数如果相等,那么公约数为他们中的一个,当两个数不相等时,用大数减小数得到的差和之前的那个较小的数再次相减,直到两个数相等,得到最大公约数。这个程序的代码量较少。

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include<stdlib.h>
    int main() 
    {
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf_s("%d%d", &a, &b);//vs更安全
    	while ((a - b) != 0) 
    	{
    		if (a > b) 
    		{
    			a = a - b;
    		}
    		else 
    		{
    			b = b - a;
    		}
    	}
    	system("cls");
    	printf("最大公约数为:%d\n", b);
    	system("pause");
    	return 0;
    }
    

    4、stein算法
    在上述2、3两种方法的基础上进行更多的优化,有了stein算法,只有比较、移位、减法或者求余,更加的便捷。
    用到了几个概念,惰性运算,移位等于除以二,和1求&的关系

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    int main()
    {
    	int a = 0;
    	int b = 0;
    	printf("请输入两个整数:");
    	scanf_s("%d%d", &a, &b);
    	int gcd = 0;//gcd最大公约数
    	int k = 1;
    	while ((!(a & 1)) && (!(b & 1)))//&&是惰性运算,当前面为假的时候就不执行后面了,||也是惰性运算,如果前面为真就不执行后面了。
    	{
    		k <<= 1;//用k记录全部公因子2的乘积 乘以2;
    		a >>= 1;//2进制位移一个单位就是除以2
    		b >>= 1;
    	}
    	while (!(a & 1))//偶数和1&得到的是0,奇数是1
    		a >>= 1;
    	while (!(b & 1))
    		b >>= 1;
    	if (a < b)
    	{
    		a ^= b, b ^= a, a ^= b;//交换,使a为较大数; 
    	}
    	while (a != b)
    	{
    		a -= b;
    		if (a < b)
    		{
    			a ^= b, b ^= a, a ^= b;//交换
    		}	
    	}
    	gcd = k * a;
    	system("cls");
    	printf("最大公约数为:%d\n", gcd);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • C语言:求两个数最大公约数和最小公倍数

    万次阅读 多人点赞 2019-06-19 16:31:03
    C语言:求两个数最大公约数和最小公倍数 求两个数最大公约数:“辗转相除法”: 设两为a和b(a>b),用a除以b,得a÷b=商…余数,若余数为0 ,则最大公约数为b;若余数不为0 ,则再用b÷余数, 得b÷余数=商1...

    C语言:求两个数的最大公约数和最小公倍数

    求两个数的最大公约数:“辗转相除法”:
    设两数为a和b(a>b),用a除以b,得a÷b=商…余数,若余数为0 ,则最大公约数为b;若余数不为0 ,则再用b÷余数,
    得b÷余数=商1…余数1,若余数1=0,则最大公约数为余数,若余数1不为0,继续让商÷余数n,一直到能够余数为零
    这时的除数即最大公约数。
    求两个数的最小公倍数:
    最小公倍数=两数的乘积÷最大公约数

    #include <stdio.h>
    #define MAX(a,b) (a>b)?a:b
    #define MIN(a,b) (a<b)?a:b
    int main()
    {
    	int a,b;
    	int yu;
    	int m,n;
    	printf("input two numbers:\n");
    	scanf("%d,%d", &m, &n);
    	a =MAX(m,n);
    	b= MIN(m,n);
    	while (a%b != 0)
    	{
    		yu = a%b;
    		a = b;
    		b = yu;
    	 }
    	printf("最大公约数为:%d\n", b);
    	printf("最小公倍数为:%d",m*n/b);
    	return 0;
    }
    
    展开全文
  • 使用c++求两个数最大公约数(适用于初学者,易懂) 我大一,才学习c++,希望分享一些我写过的程序,有一些地方不好理解的地方我有重点备注,希望对你们有用。笔芯
  • 主要介绍了PHP编程求最大公约数与最小公倍数的方法,涉及php数学计算的相关运算技巧,需要的朋友可以参考下
  • 求两个数最大公因数的c语言程序

    万次阅读 2018-09-24 20:39:33
    对于这问题,我能想到的方法有三种: ...这时的i就为最大公因数 程序如下: #define _CRT_SECURE_NO_WARNINGS #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; int main(){ int a ...

    对于这个问题,我能想到的方法有三种:

    ①先找出这两个数中最小的那个,可以用i表示,然后用这两个数依次对i取余. 同时i不断减1,直到这两个数对i取余都为0;这时的i就为最大公因数

    程序如下:

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    int main(){
    	int a = 0;
    	int b = 0;
    	int i = 0;
    	printf("输入 a b:");
    	scanf("%d%d", &a, &b);
    	if (a > b){
    		i = b;
    	}
    	else i = a;
    	while (a%i != 0 || b%i != 0){
    		i--;
    	}
    	printf("最大公因数为%d\n", i);
    	system("pause");
    	return 0;
    }

    ②辗转相除法:用其中一个数除以另外那个数,再用除数除以得到的余数,重复这个过程,直到余数为0.余数为0的等式中那个除数就是最大公因数.

    程序如下:

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    int main(){
    	int a = 0;
    	int b = 0;
    	int i = 1;
    	printf("输入 a b:");
    	scanf("%d%d", &a, &b);
    	if (a == b){
    		printf("最大公因数为%d\n", a);
    	}
    	else {
    		while (i != 0){
    			i = a%b;
    			a = b;
    			b = i;
    		}
    		printf("最大公因数为%d\n", a);
    	}
    	system("pause");
    	return 0;
    }

    ③更相减损术:用较大的那个数减去较小的那个数,再用减数和差中,较大的那个减去较小的那个,重复这个过程,直到减数和差相等.减数就为最大公因数.

    程序如下:

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    int main(){
    	int a = 0;
    	int b = 0;
    	int i = 1;
    	printf("输入 a b:");
    	scanf("%d%d", &a, &b);
    	if (a == b){
    		printf("最大公因数为%d\n", a);
    	}
    	else {
    		while (a != b){
    			if (a > b)  a = a - b;
    			if (a < b)  b = b - a;
    		}
    		printf("最大公因数为%d\n", a);
    	}
    	system("pause");
    	return 0;
    }

    以上就是这三种方法的程序代码,当然我目前只知道这三种方法,其他方法还不是很了解.

    展开全文
  • 求两个数最大公约数和最小公倍数工具
  • 求最大公约数和最小公倍数. 相信你们会找到的。
  • 三种方法求两个数最大公因数

    万次阅读 2018-09-08 17:17:10
    求两个正整数的最大公约数和最小公倍数。 基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决最大公约数问题,提供友好的输入输出。 提高要求:1.三种以上算法解决两个正整数最大公约数问题。 2....
  • python实现求两个数最大公因数

    千次阅读 2020-10-24 14:04:15
    编写函数,求两个数最大公因数。编写主程序,输入两个整数,调用函数求最大公因数,在主程序中输出最大公因数。 代码: ''' 编写函数,求两个数最大公因数。 编写主程序,输入两个整数, 调用函数求最大公因数...
  • 包含两个算法,一个为辗转相除法,一个为连续整数检测法。而且算法中加入计数法对比两种算法的时间复杂度。
  • C语言求两个数最大公约数的三种算法

    万次阅读 多人点赞 2018-11-02 16:56:19
    1.相减法 #include&lt;stdio.h&gt; //相减法 int main() ...输入两个数字求最大公约数:"); scanf("%d%d",&amp;a,&amp;b); while(a!=b) { if(a&gt;b) ...
  • a=int(input()) ... print("最大公约数为:",i) break print("最小公倍数为:",a/i*b) python3 中for循环想要递减必须用到range函数的第三参数及递增量,递增量可以为负数。 for i in range(5,0,-1.
  • python-求两个数最大公约数

    千次阅读 2019-01-22 23:04:43
    求两个数最大公约数。(10分) 题目内容: 输入两个正整数num1和num2(不超过1000),它们的最大公约数并输出。 我们定义求最大公约数的函数为hcf,给出程序主体如下: num1=int(input("")) num2...
  • 求两个数最大公约数 一、 问题描述与分析 二、 算法设计(或算法步骤) 1. 欧几里得算法 2. 枚举法 3. 公共因子积 4. 更相减损术 5. Stein算法 求两个数最大公约数 一、问题描述与分析 设有 m 和 n 两个正整数,...
  • 最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个; a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号; 求最大公...
  • Java实现:求两个数最大公约数

    千次阅读 2020-02-18 23:06:03
    title: Java实现:求两个数最大公约数 tags: java 算法 categories: 个人笔记 copyright: true abbrlink: f202 date: 2019-12-07 16:44:58 求解两个数最大公约数的几种方法的比较 1. 暴力枚举法 优点:思路...
  • #define _CRT_SECURE_NO_WARNINGS 1 include &amp;amp;lt;stdio.h&amp;amp;gt; #include&...printf(“请输入两个数:”); scanf(&amp;quot;%d%d&amp;quot;, &amp;amp;amp;a, &
  • 最小公倍数呢,它与最大公约数的乘机为所求数之积。 比如 x,y的最大公约数和最小公倍数 记住这公式: x×y=最小公倍数×最大公约数 二、求最大公约数的三种方法 ①辗转相除法 int measure(int x, int y) { ...
  • 求两个数最大公约数(C++)

    万次阅读 多人点赞 2019-03-07 22:19:45
    求两个数最大公约数(C++) 一.算法构造 1.辗转相除法 设两为a,b设其中a 做被除,b做除数,temp为余数 ①大数放a中、小数放b中; ②a/b的余数;temp=a%b ③、若temp=0则b为最大公约数; ④、如果temp!=0则把b...
  • 给定两个自然数,两个数最大公约数。 分析: 单看题目的话,非常简单,我们可以循环遍历自然数,如果能够整除两个自然数,就把这个记下来,在这些记录中找到最大的一个。 但是这样做有几个缺点:一是做除...
  • 主要介绍了输入两个正整数m和n,最大公约数和最小公倍数,需要的朋友可以参考下
  • 编写一个子函数fn1,用来求两个正整数的最大公约数:编写一个函数fn2,用来求两个正整数的最小公倍数:编写主函数,从键盘读入两个正整数,分别调用fn!和f几2,计算并输出这两个数最大公约数和最小公倍数d测试要点:离...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,261
精华内容 18,504
关键字:

求两个数的最大公约数