精华内容
下载资源
问答
  • 如果给定两个数,要求你求出两个数的最大公约数,该怎么求?最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。我们可以通过一个递归的方法来实现源代码如下:/*/ * @ly * 欧几里得...

    如果给定两个数,要求你求出两个数的最大公约数,该怎么求?

    最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。

    我们可以通过一个递归的方法来实现

    源代码如下:

    /*/
     * @ly
     * 欧几里得算法,求最大公约数,辗转相除法。
     */
    import java.util.*;


    public class OuJiLiDe {
         public static int gcd(int m,int n) {
        if(n==0) return m;    //两个数中若其中一个为0那么最大公约数必然是另一个不为0的数
        else {
        int r = m%n;    //将两个数进行模运算,如果模为0,那么最大公约数就是n
        return gcd(n,r);  //递归调用,模不为0的时候
        }
         }
    public static void main(String[] args) {
               Scanner input = new Scanner(System.in);
               int a = input.nextInt();
               int b = input.nextInt();
               System.out.println("a和b的最大公约数是:"+gcd(a,b));
               input.close();
    }


    }

    展开全文
  • 对于求两个数的最小公倍数与最大公约数最大公约数等于两数相乘再除以最大公约数,所以问题的核心就是怎么求最大公约数。我所知道的有四种方法:穷举法(不推荐使用),辗转相除法(使用最多),更相减损术,Stein...

    求两个数的最大公约数与最小公倍数

    对于求两个数的最小公倍数与最大公约数,最大公约数等于两数相乘再除以最大公约数,所以问题的核心就是怎么求最大公约数。我所知道的有四种方法:穷举法(不推荐使用),辗转相除法(使用最多),更相减损术,Stein算法(密码领域用的多)

    穷举法(暴力搜索)

    穷举法就不多解释了直接给代码

    int GCD1(int a,int b)//暴力搜索
    {
        int gcd=(a>b?b:a);
        for(int i=gcd; i>0; i--)
        {
            if(a%i==0&&b%i==0)
            {
                gcd=i;
                break;
            }
        }
        return gcd;
    }
    

    辗转相除法(欧几里得算法)

    辗转相除法分如下两部步:

    1. 较大数a对教小数b进行取余运算得到余数c;
    2. 若余数为零,则较小数为最大公约数;否则令a=b,b=c重新执行第一步

    递归代码如下(要求a,b按大小输入):

    int GCD2(int a,int b)//辗转相除
    {
        return b==0?a:GCD2(b,a%b);
    }
    

    非递归代码如下:

    int GCD2(int a,int b)//辗转相除
    {
        int big,small;
        if(a>b)
        {
            big=a;
            small=b;
        }
        else
        {
            big=b;
            small=a;
        }
        for(int i=big%small; i>0; i=big%small)
        {
                big=small;
                small=i;
        }
        return small;
    }
    

    更相减损术

    更相减损术用的是减法而不是除法,具体步骤如下:

    1. 两数若都为偶数则两数一直都除以2到不都为偶数,并记录除以了几个2;
    2. 较大数a减较小数b得到差值c;
    3. 若c与b相等,则c为最大公约数,否则令a=max(b,c),b=min(b,c)再执行第二步;

    代码如下:

    int GCD3(int a,int b)//更相减损术
    {
        int mul=1;
        int big,small;
        if(a>b)
        {
            big=a;
            small=b;
        }
        else
        {
            big=b;
            small=a;
        }
        while(1)
        {
            if(big%2==0&&small%2==0)
            {
                mul*=2;
                big/=2;
                small/=2;
            }
            else break;
        }
        for(int i=big; i!=small; i=big-small)
        {
            if(i>small)
            {
                big=i;
            }
            else
            {
                big=small;
                small=i;
            }
        }
        return small*mul;
    }
    

    Stein算法

    欧几里得算法与更相减损术的缺陷
           欧几里德算法是计算两个数最大公约数的传统算法,无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷,这个缺陷在素数比较小的时候一般是感觉不到的,只有在大素数时才会显现出来。
           更相减损术在两数相差较大时,会进行多次无意义运算,两数相差越大,无意义运算越多,效率过低。
           一般实际应用中的整数很少会超过64位(当然已经允许128位了),对于这样的整数,计算两个数之间的模是很简单的。对于字长为32位的平台,计算两个不超过32位的整数的模,只需要一个指令周期,而计算64位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过64位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多CPU时间。对于现代密码算法,要求计算128位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模。于是便有了Stein算法。
    算法的思想
    由J. Stein 1961年提出的Stein算法很好的解决了欧几里德算法中的这个缺陷,Stein算法只有整数的移位和加减法,为了说明Stein算法的正确性,首先必须注意到以下结论:

    1. gcd(a,a)=a,也就是一个数和其自身的公约数仍是其自身。
    2. gcd(ka,kb)=k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换。特殊地,当k=2时,说明两个偶数的最大公约数必然能被2整除。
    3. 当k与b互为质数,gcd(ka,b)=gcd(a,b),也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地,当k=2时,说明计算一个偶数和一个奇数的最大公约数时,可以先将偶数除以2。

    算法的步骤

    1. 两数若都为偶数则两数一直都除以2到不都为偶数,并记录除以了几个2;
    2. 若两数中还有非偶数,将其除以2至奇数
    3. c=|数a-数b|,d=min(数a,数b),
    4. 若c为0则d为最大公约数,否则令a=c,b=d重复第二步

    代码如下:

    int GCD4(int a,int b)//Stein
    {
        int mul=1;
        while(1)
        {
            if(a%2==0&&b%2==0)
            {
                a>>=1;
                b>>=1;
                mul<<=1;
            }
            else if(a%2==0)
            {
                a>>=1;
            }
            else if(b%2==0)
            {
                b>>=1;
            }
            else break;
        }
        while(a>0)
        {
            while(a%2==0)
            {
                a>>=1;
            }
            int abs=fabs(a-b);
            int small=a>b?b:a;
            a=abs;
            b=small;
        }
        return b*mul;
    }
    

    c++代码

    具体实现代码及效果图:

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int GCD1(int a,int b);//暴力搜索
    int GCD2(int a,int b);//辗转相除
    int GCD3(int a,int b);//更相减损术
    int GCD4(int a,int b);//Stein算法
    int main()
    {
        int a=0,b=0;
        int gcd[4]= {1,1,1,1}; //最大公约数:greatest common divisor(gcd)
        int lcm[4]= {1,1,1,1}; //最小公倍数:least common multiple(lcm)
        while(cin>>a>>b)
        {
            gcd[0]=GCD1(a,b);
            gcd[1]=GCD2(a,b);
            gcd[2]=GCD3(a,b);
            gcd[3]=GCD4(a,b);
            for(int i=0; i<4; i++)
            {
                lcm[i]=a*(b/gcd[i]);//先算除法防止越界
                cout<<gcd[i]<<" "<<lcm[i]<<endl;
            }
        }
        return 0;
    }
    

    效果图
    萌新一个,若代码有错误或算法思想有问题还望多多斧正;

    展开全文
  • 三种方法求最大公约数和最小公倍数标题 首先明确最大公约数和最小公倍数的关系,设两个数为a,b;最大公约数为c,最大公倍数为d; 则ab=cd;怎么得到的可以通过数学算式证明。 分别用暴力搜索法,辗转相除法,更相减...

    三种方法求最大公约数和最小公倍数标题

    首先明确最大公约数和最小公倍数的关系,设两个数为a,b;最大公约数为c,最大公倍数为d;
    则ab=cd;怎么得到的可以通过数学算式证明。
    分别用暴力搜索法,辗转相除法,更相减损法求最大公约数,求出最小公约数就求出了最小公倍数。

    #include<iostream>
    using namespace std;
    int main()
    {
    	//变量a,b为所求的两个数,由键盘输入;c是最大公约数,i为控制循环变量的整数,
    	//t为每种方法需要用到的整数 
    	int a,b,c=0,i;
    	cout<<"请输入两个整数,求它们的最小公倍数"<<endl;
    	cin>>a>>b;
    	
    	
    	for(a>b?i=b:i=a;i>=1;i--)					//暴力搜索法求公约数 
    	    if(a%i==0&&b%i==0)
    		  {
    	    	c=i;
    			break;
    		  }		
    	cout<<"暴力搜索法求解最小公倍数:"<<a*b/c<<endl;             
    	  //根据最大公约数和最小公倍数之间的关系输出最小公倍数
    	  
    	  
    	int t1=a,t2=b; 								//辗转相除法求公约数 
    	while(t1%t2!=0)						    	//辗转相除循环 
    	{		  
    		  int t3=t2;
    		  t2=t1%t2;
    	      t1=t3;
    		  	
    	}
    	c=t2;
    	cout<<"辗转相除法求最小公倍数:"<<a*b/c<<endl;	
    
    
    
        int t4,t5;									//更相减损法求公约数 
    	if(a>b)
    	t4=a,t5=b;
    	else 
    	t4=b,t5=a;
    	c=t4-t5;								//初始化公约数 
    	while(t5!=c)
    	{
    		t5>c?t4=t5,t5=c:t4=c;			 
    		c=t4-t5;					//相减
    	}
    	cout<<"更相减损法求最小公倍数:"<<a*b/c<<endl;	
    	
    	return 0;
    	
    }
    
    展开全文
  • python怎么求最大公约数和最小公倍数 一、求最大公约数 用辗转相除法求最大公约数算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25,25除以10商2余5,那么10...
  • 新手学习编程包括我在内(同为菜鸟),经常会遇到求最大公约数最小公倍数的问题,并且容易忘记,为了牢牢记住,现在我们谈论怎么用c语言解决它。 最大公约数 最大公约数通常有三种实现方法,这里体现其中两种。 ...

    最大公约数和最小公倍数

    新手学习编程包括我在内(同为菜鸟),经常会遇到求最大公约数最小公倍数的问题,并且容易忘记,为了牢牢记住,现在我们谈论怎么用c语言解决它。

    最大公约数

    最大公约数通常有三种实现方法,这里体现其中两种。

    1.辗转相除法:

    具体的步骤就是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。最后的除数就是这两个数的最大公约数。

    例如: 3 和 8

    8 % 3 = 2
    3 % 2 = 1
    2 % 1 = 0
    1即为最大公约

    /辗转相除
    #include <stdio.h>
    void GreatCommonDivisor(int a,int b)
    {
    	int c = 0;
    	while(a != 0 || b !=0)
    	{
    		if(a < b)
    		{
    			c = a;
    			a = b;
    			b = c;
    		}
    		a = a%b;
    			if(a == 0)
    			{
    				break;
    			}
    	}
    	printf("c = %d\n",b);
    }
    
    int main()
    {
    	
    	GreatCommonDivisor(1,3);
    	GreatCommonDivisor(5,5);
    	GreatCommonDivisor(9,18);
    	GreatCommonDivisor(45,25);
    	GreatCommonDivisor(47,25);
    	return 0;
    }
    

    在这里插入图片描述

    2.更像相减法:

    更相减损法是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。
    例如: 3 和 8
    8 * 3 = 5
    5 - 3 = 2
    3 - 2 = 1
    2 - 1 = 0
    1即为最大公约

    //相减法
    #include<stdio.h>
    void GreatCommonDivisor(int a,int b)
    {
    	int c = 0;
    	while(a != 0 && a > 0)
    	{
    		if(a <= b)
    		{
    			c = a;
    			a = b;
    			b = c;
    		}
    			a = a-b;
    	}
    	printf("c = %d\n",b);
    }
    int main()
    {
    	GreatCommonDivisor(1,3);
    	GreatCommonDivisor(5,5);
    	GreatCommonDivisor(9,18);
    	GreatCommonDivisor(45,25);
    	GreatCommonDivisor(47,25);
    	return 0;
    	}
    

    在这里插入图片描述

    最小公倍数:

    求最小公倍数相对来说就比较简单了。只需要先求出最大公约数。用两个数的乘积除以最大公约数即可。

    int  Thegreatdivisor(int n,int m)最大公约数
    {
    	int tmp;
    	while(n != 0)
    	{
    		if(n < m)
    		{
    			tmp = n;
    			n = m;
    			m = tmp;
    		}
    		n %= m;
    	}
    	printf("min = %d\n",m);
    	return m;
    }
    
    
    void Least_common_multiple(int n,int m)///最小公倍数
    {
    	
    	int max = (n*m)/Thegreatdivisor(n,m);
    	printf("max = %d\n",max);
    }
    int main()
    {
    	Least_common_multiple(1,3);
    	Least_common_multiple(5,10);
    	Least_common_multiple(45,10);
    	Least_common_multiple(9,3);
    	return 0;
    }
    

    输出结果:
    在这里插入图片描述

    展开全文
  • 求最大公约数时,最好的方法使用欧几里得算法。 欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。 代码示例: ...
  • 上次写在刷OJ的时候有一道题要对一个分数进行约分,即要求出最大公约数....1. 求最大公约数算法 代码非常简单,只需要用一个简单的递归就解决了 int gcc(int a, int b) { return b == 0 ? a : gcc(b, a % b); } 2....
  • 本人菜鸟一枚,上午在看书的时候突然看到了求最大公约数的一个例题,突然就想到以前好像看过一个欧几里得算法,故又上网仔细找了一下欧几里得算法的原理。可能是本人时间长没看算法,脑子都生锈了。 看了几个讲解...
  • 刚好复习一下怎么求最大公约数,大一上学python的时候想破脑袋都做不出来的题目,现在想想当初的自己是真的菜。。 Problem B: 深入浅出学算法001-求最大公约数 Time Limit: 1 Sec Memory Limit: 64 MB Submit: 3982 ...
  • 数学问题算法求最大公约数和最小公倍数,摘自C语言网,看看怎么完成的吧。 题目: 输入两个正整数m和n,最大公约数和最小公倍数。 1.程序分析:利用辗除法。 更多例题来自C语言网题库:...
  • 关于求最大公约数

    2010-09-13 23:42:00
    网上查询了一下资料,讲到的求最大公约数的最经典的算法——欧几里德算法,也叫做辗转相除法吧。 大概思路是这样的: 欲求两个正整数m,n的最大公约数gcd(m,n): r = m %n; m = n; n ...
  • 首先,来看看怎么求最大公约数,求最大公约数需要用到欧几里得算法,也称为辗转相除法。算法就是用两数中较大的数a除以另一个数b得出余数c,然后判断c是否为0(意思a能够整除b),为0则b为最大公因数;反之,则把b...
  • 两个数的最大公约数怎么求? 思考题目的同时,我在这也顺便发出三个灵魂疑问? 什么又是更相减损法? 什么又是辗转相除法? 什么又是欧几里得算法? 不懂没关系,往下看 要解决两数的最大公约数问题?,你首先要知道...
  • 转自:http://www.cnblogs.com/dah/archive/2007/03/06/666114.html 今天上课老师问"辗转相除法"又叫什么算法..居然没人知道..... 但也忘了是怎么辗转相除的.. 特此"百度知道"之:Euclid欧几里德算法
  • 好吧,说实话是实在不喜欢算法,因为我数学一直很垃圾,150分的题,高中三年,150分的题,很少有上90的情况,99%是在70分上下晃悠... 假设有整数x,y,要求这两个数的最大公约数怎么做?首先思路分析:先出x和y...
  • 看下面的一段代码 int(int x,int y) { int temp;  while(x)  { temp=x; x=y%x; y=temp;}  }  return y;  }  这是x,y最大公约数的代码,那么我们应该怎么理解他的算法精髓呢。
  • 不知道公约数和公倍数怎么求,只知道最大公约数是最大的共同因子,最大公倍数是最小的公共倍数(这个都不知道那就GG)。 提供的思路:先找出m和n所有的因子然后找出m和n相等的因子(公因子),最后找到其中最大因子,...
  • 最大公约数

    2012-04-06 19:27:30
    辗转相除,又名欧几里德算法(Euclidean algorithm),是两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》中,而在中国则可以追溯至东汉出现的《九章...
  • 前几天有人问我两个整数的最大公约数怎么求,最近工作也不是太忙,就整理了一下关于整数的一些操作和算法,比如:最大公约数、最小公倍数、质数、合数、奇数、偶数、2的整数次幂、完全平方数等。代码中可能了会有点...
  • 怎么求这两个数的最大公约数与最小公倍数。 首先想到地就是辗转相除法来求解这道题目。 算法思想如下: 设两数为a、b(a>b),求a和b最大公约数(a,b)的步骤如下:用a除以b,得a÷b=q......r1(0≤r1)。若r1=0,则(a,b...
  • (唉,还是打算用csdn吧,毕竟太多IT大牛在这,为了approach大牛,哥还是乔迁了。)——这是废话  昨天晚上感觉,...之前看《算法导论》的时候就再想辗转相除法就怎么被发现了,今天再好好想想毕达哥拉斯学派的基
  • 《Raptor程学设计案例教程》清华大学出版社 ...关键是前5千年怎么计算的问题,前5千年可以输入负数年份,然后取绝对值进行计算 这个题的循环次数是-2986年到2014年. P19-10 蚂蚁爬格的问题运用rapto...
  • 数学--数论--最小公倍数+最大公约数

    千次阅读 2019-11-30 15:35:21
    GCD(a,b)为a ,b的最大公因数 LCM(a,b)为小公倍数 必须要知道的公式: a*b = gcd(a,b) * lcm (a,b) 先说GCD怎么求: int gcd(int a,int b){ return __gcd(a,b); //不是我闹着玩,是真有这个函数 } 正经的来了,...
  • 辗转相除,又名欧几里德算法(Euclidean algorithm),是两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》中,而在中国则可以追溯至东汉出现的《九章...
  • while(n != 0) { r = m % n; m = n; n = r; } printf("Their greatest common ...都知道在最大公因子(最大公约数)的时候,使用欧几里得算法(辗转相除法)。下面来研究这个算法怎么推论出来的。 首先看
  • 算法练习-蓝桥杯练习系统-算法训练-ALGO-2 最大最小公倍数(※包括最大公约数、最小公倍数的总结) 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 已知一个正整数N,问从1~N中任选出三个数,他们的最小公...
  • 辗转相除法又名欧几里得算法,是求最大公约数的一种算法,英文缩写是gcd。所以如果你在大牛的代码或者是书上看到gcd,要注意,这不是某某党,而是指的辗转相除法。 在介绍这个算法之前,我们先来看下最大公约数问题...
  • 题目要求 编写函数,用辗转相除法,...怎么理解呢,比如 10和15的最大公约数,在数学的一般是怎么算的 15 /10 =1 余 5 10 / 5 = 2 余 0 以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,..
  • 我们不妨先来复习一下欧几里得辗转相除法是怎么求两个数的最大公约数的 求 4453 和 5767 的最大公约数时,可作如下除法. 5767÷4453=1 余 1314 4453÷1314=3 余 511 1314÷511 =2 余 292 511 ÷292 =1 余 ...
  • 有两个数 a b,现在,我们要求 a b 的最大公约数怎么求?枚举他们的因子?不现实,当 a b 很大的时候,枚举显得那么的naïve ,那怎么做? 欧几里德有个十分又用的定理: gcd(a, b) = gcd(b , a%b) ,这样,...

空空如也

空空如也

1 2 3 4 5 6
收藏数 115
精华内容 46
关键字:

最大公约数怎么求算法