精华内容
下载资源
问答
  • 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;
    }
    
    展开全文
  • 三种方法求两个数最大公因数

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

    1.题目描述:

    求两个正整数的最大公约数和最小公倍数。
    基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决最大公约数问题,提供友好的输入输出。
    提高要求:1.三种以上算法解决两个正整数最大公约数问题。
    2.求3个正整数的最大公约数和最小公倍数。

    2.程序源码及解题原理

    (1)相减法(C/C++)

    原理:有两整数a和b:
    ① 若a>b,则a=a-b
    ② 若a

    (2)穷举法(C/C++)

    原理:
    有两整数a和b:
    ① i=1
    ② 若a,b能同时被i整除,则t=i
    ③ i++
    ④ 若 i <= a(或b),则再回去执行②
    ⑤ 若 i > a(或b),则t即为最大公约数,结束
    源码:
    #include

    改进后求两个数的最大公因数和最小公倍数:

    ① i= a(或b)
    ② 若a,b能同时被i整除,则i即为最大公约数,
    结束
    ③ i–,再回去执行②
    源码:
    #include

    多个数的最大公因数:

    #include

    (3)辗转相除(JAVA)

    原理:
    用辗转相除法求两个数的最大公约数的步骤如下:
    先用小的一个数除大的一个数,得第一个余数;
    再用第一个余数除小的一个数,得第二个余数;
    又用第二个余数除第一个余数,得第三个余数;
    这样逐次用后一个数去除前一个余数,直到余数是0为止。那么,最后一个除数就是所求的最大公约数(如果最后的除数是1,那么原来的两个数是互质数)。
    例如:求1515和600的最大公约数,
    第一次:用600除1515,商2余315;
    第二次:用315除600,商1余285;
    第三次:用285除315,商1余30;
    第四次:用30除285,商9余15;
    第五次:用15除30,商2余0。
    1515和600的最大公约数是15。
    辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数,可以先求两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数。这样依次下去,直到最后一个数为止。最后所得的一个最大公约数,就是所求的几个数的最大公约数。
    Java源码:
    package test;

    import java.util.Scanner;
    public class zuoye {
    /**
    * @max_num:最大公因数
    * @ min_num:最小公倍数
    */
    public static void main(String[] args) {
    @SuppressWarnings(“resource”)
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    System.out.println(max_num(a,b));
    System.out.println(min_num(a,b));
    }
    private static int max_num(int a, int b) {
    int max,min;
    max=(a>b)?a:b;
    min=(a

    展开全文
  • 求两个数最大公约数,可以用四种方法,分别是暴力穷举法(不适用于大数字)、辗转相除法(线性代数)、更相减损法(九章算术)、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;
    }
    
    展开全文
  • /求两个数最大公约

    /求两个数的最大公约 数

    include

    int main()
    {
        int i = 0,j=0,n1=0,n2=0,a[100],max=0;
    
        printf("请输入n1:");
        scanf("%d", &n1);
        printf("请输入n2:");
        scanf("%d", &n2);
        for (i = 1; (i <= n1) && (i <= n2); i++)
        if (n1% i == 0 && n2 % i == 0)
            {
    
                a[j] = i;//将两个数所以的公因数存在一个数组里
                j++;
    
            }
        for (i = 0; i < j;i++)//找出数组中的最大公因数
        if (a[max] < a[i])
            max = i;
        printf("输出最大公约数:");
        printf("%d\n", a[max]);
        system("pause");
        return 0;
    }

    //求两个数的最大公约数

    include

    int main()
        {
        int a, b, i, n;
        printf("请输入两个数:");
        scanf("%d%d", &a, &b);
        n = a;
        if (n > b)//找出两个数中的最大数
            n = b;
    
        for (i = n; i >= 1; i--)
        {
            if (a%i == 0 && b%i == 0)
            {
                printf("最大公约数:=%d\n", i);
                break;
            }
        }
         system("pause");
        return 0;
    }

    //求最大公约数

    include

    int main()
    {
        int a = 18;
        int b = 24;
        int tmp = 0;
        int i = 0;
        while (tmp = a%b)
        {
            a = b;
            b = tmp;
        }
        printf("%d\n", b);
        system("pause");
        return 0;
    }
    
    
    展开全文
  • 用 Java实现 输入两个数 求两个数最大公约数,如何使用java语言求两个数最大公约数
  • 求两个数最大公约数

    2015-10-29 19:28:15
     写一个程序,求两个正数的最大公约数。如1100100210001,120200021,最大公约数 分析:设两个数分别为x,y  最大公约数f(x,y),如果有x%2==0而y%2不等于0,那么可以  约简为f(x/2,y),同样道理适用于y ...
  • 下面写的是一个用辗转相除法求两个数公约数的代码,我们先来了解什么是辗转相除法。  举个例子:128 和48的最小公约数  辗转相除法就是用一个模上另一个(如a%b)的余数如果等于零,则b为两最小公约数...
  • 编写一个子函数fn1,用来求两个正整数的最大公约数:编写一个函数fn2,用来求两个正整数的最小公倍数:编写主函数,从键盘读入两个正整数,分别调用fn!和f几2,计算并输出这两个数最大公约数和最小公倍数d测试要点:离...
  • 算法 - 求两个自然数的最大公约数(C++)

    万次阅读 多人点赞 2019-02-27 20:28:10
    分享一个大牛的人工智能教程。... * 求两个自然数的最大公约数 - C++ - by Chimomo * * Answer:辗转相除法 */ #include &lt;iostream&gt; #include &lt;cassert&gt; #include &...
  • C语言 | 求两个数最大公约数的四种算法

    千次阅读 多人点赞 2020-10-20 20:58:28
    最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。求解的方式比较多,暴力穷举、辗转相除法、更相减损法、Stein算法。 1.暴力穷举法 如果大数可以整除小数,那么最大公约数为小数。...
  • python实现求两个数最大公因数

    千次阅读 2020-10-24 14:04:15
    编写函数,求两个数最大公因数。编写主程序,输入两个整数,调用函数求最大公因数,在主程序中输出最大公因数。 代码: ''' 编写函数,求两个数最大公因数。 编写主程序,输入两个整数, 调用函数求最大公因数...
  • python-求两个数最大公约数

    千次阅读 2019-01-22 23:04:43
    求两个数最大公约数。(10分) 题目内容: 输入两个正整数num1和num2(不超过1000),它们的最大公约数并输出。 我们定义求最大公约数的函数为hcf,给出程序主体如下: num1=int(input("")) num2...
  • 求两个数最大公因数的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 ...
  • C语言如何求两个数最大公约数 思维:辗转相除法 分析过程: 给定两个整数,运用辗转相除法,辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。 例如,(319,377): ∵ 319÷377=0(余319)...
  • 输入两个数两个数最大公约数输入连个,两个数最大公约数:分析: 最大公约数:这个两个数能同时被一个整除,那么这个就是这两个数公约数,那么最大公约数就是这两个整数的所有质数约数的乘积。...
  • 求两个数最大公约数,欧几里得算法,这两种方法除第一种可以避免除数为零的情况,两者有什么区别?谢谢 public static int gcd(int p, int q) { if (q == 0) return p; int r = p % q; return gcd(q, r) ; } ...
  • 求两个数最大公约数 一、 问题描述与分析 二、 算法设计(或算法步骤) 1. 欧几里得算法 2. 枚举法 3. 公共因子积 4. 更相减损术 5. Stein算法 求两个数最大公约数 一、问题描述与分析 设有 m 和 n 两个正整数,...
  • #define _CRT_SECURE_NO_WARNINGS #include <... //求两个数最大公约数 //第一种方法 /*int a, b; int min; int max = 0; //max用来记录最大公约数 printf("请输入两个数: \n"); scanf...
  • (1)用短除法求两个数最大公约数,一般先用这两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来,在除的过程中,有时也可以用两个数公约数去除。 (2)求两个数
  • 输入两个数字,可以两个数字的最大公约数和最小公倍数。输入的两个数字之间用空格隔开。输入之后回车确定
  • 求两个数最大公约数(三种方法)

    万次阅读 多人点赞 2018-10-07 10:36:21
    方法1:通过辗转相除法来求两个数最大公约数 //思路 //排序:首先创建一个临时变量,然后将两个数排序,将较大的存入a中,将较小的存入b中 //创建一个while循环,用较大的去反复取余较小的,并将取余得到的结果...
  • 思路:求两个数最大公约数,首先要确定两个数中哪个最大,假设我们让a大b小,那么这两个数之间的最大公约数的范围就在1~b之间,从b开始找两个数公约数公约数是能让两个数同时整除的),第一个找到的公约数...
  • 求两个数最大公约数,我们首先想到的是,创建一个中间变量,让两个数改变,直到最后不能模后,则可出来最大公约数
  • 穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤: 从两个数中较小开始由大到小列举,直到找到公约数立即中断列举,得到的...穷举法求两个数最大公约数代码: import java.util.Scanner; publ
  • 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) ...
  • 1、计算两个整数的最大公约数方法有两种 第一种是使用《九章算术》中的更相减损术方法,“以少减多,更相减损,其等也,以等约之,等约之,即除也,其所以相减者皆等之重叠,故以等约之。”其大概意思就是“若...
  • 输入描述: 输入数据含有不多于50对的数据,每对数据由两个正整数...求两个数最大公约数,可以采用欧几里得方法: 只要两个数不相等,就反复用大的去减小的,直到相等为止,此相等的就是最大公约数 代码...
  • 求两个正整数a,b的最大公约数p和最小公倍数q。 最原始的方法是,p初始化为min(a, b),这里假设a  然后检测p能否同时整除a,b,是则停止循环,  否则令p -= 1,继续检测 对于q,则将其初始化为max(a,b) = b, 则...
  • 【C++】求两个数最大公约数——方法大全!!

    千次阅读 多人点赞 2019-06-02 17:53:43
    输入两个数求最大公约数。 主要算法及示例 1. 查找约数法 先分别找出两个数各自所有的约数,再从两个数的约数中找到公有的约数,其中最大的那个公有约数就是要求的最大公约数。 主要适合两个数都较小...
  • 两种方法求两个数最大公约数和最小公倍数

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,461
精华内容 18,184
关键字:

求两个数的最大公因数的方法