求最大公约数的4种常用算法是什么_用辗转相除法求最大公约数

(3) 2024-06-06 09:12

Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说求最大公约数的4种常用算法是什么_用辗转相除法求最大公约数,希望能够帮助你!!!。

一、问题描述：
运行最大公约数的常用算法

二、问题分析与设计：
1.辗转相除法（又名欧几里德法）

①函数嵌套调用

其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；

代码：

#include<iostream>
using namespace std;
int divisor(int a,int b)           //自定义函数求最大公约数
{ 
   
	int temp;                   //整形零时变量
	if(a<b)                     //a<b 则交换 
	{ 
   
		temp=a;a=b;b=temp;
	}
	while(b!=0)
	{ 
   
		temp=a%b;              //a中大数除以b中小数循环取余，直到b及余数为0
		a=b;
		b=temp;
	}
	return a;                  //返回最大公约数到调用函数处
}
int multipile(int a,int b)         //自定义函数求最小公倍数
{ 
   
	int divisor(int a,int b);       //自定义函数返回值类型
	int temp;
	temp=divisor(a,b);          //再次调用自定义函数，求出最大公约数
	return(a*b/temp);           //返回最小公倍数到主调函数处进行输出
}
int main()
{ 
   
	int m,n,t1,t2;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)
	{ 
   	
		printf("请重新输入正确整数：");
		cin.clear();                //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=divisor(m,n);
	t2=multipile(m,n);
	printf("最大公因数为：%d\n",t1);
	printf("最小公倍数为：%d\n",t2);
	return 0;
}

测试及测试代码与平均运行时间：
测试代码：

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int divisor(int a,int b)
{ 
   
	int temp;
	if(a<b)
	{ 
   
		temp=a;a=b;b=temp;
	}
	while(b!=0)
	{ 
   
		temp=a%b;
		a=b;
		b=temp;
	}
	return a;
}
void main()
{ 
   
	int m[5000],n[5000],t1,i;
	clock_t start,finish;
    double duration;
	time_t t=time(NULL);
	srand(t);
	for(i=0;i<5000;i++)
	{ 
   
		m[i]=rand()%100;
		n[i]=rand()%100;
	}
	start=clock();
	for(i=0;i<5000;i++)
	{ 
   
		t1=divisor(m[i],n[i]);
		printf("%d %d %d\n",m[i],n[i],t1);
	}
	finish=clock();
	duration=(double)(finish-start)/5000;       //平均运行时间
	printf("%f milliseconds\n",duration);

}

②函数递归调用

#include<iostream>
#include<time.h>
using namespace std;
int gcd(int a,int b)                 //自定义函数求最大公约数
{ 
   
	if(a%b==0)                    //终止条件
		return b;                   //b及为最大公约数
	else
		return gcd(b,a%b);
}
int main()
{ 
   
   int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)  //判断输入两数字是否小于零或为小数
	{ 
   	
		printf("请重新输入正确整数：");
		cin.clear();            //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=gcd(m,n);
	printf("最大公因数为：%d\n",t1);
	printf("最小公倍数为：%d\n",m*n/t1);
	return 0;
}

测试及测试代码与平均运行时间：
测试代码：

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int gcd(int a,int b)
{ 
   
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}
void main()
{ 
   

	int m[2000],n[2000],t1,i;
	clock_t start,finish;
	double duration;
	time_t t=time(NULL);
	srand(t);
	for(i=0;i<2000;i++)
	{ 
   
		m[i]=rand()%100;
		n[i]=rand()%100;
	}
	start=clock();
	for(i=0;i<2000;i++)
	{ 
   
		t1=gcd(m[2000],n[2000]);
		printf("%d %d %d %d\n",m[i],n[i],t1);
	}
	finish=clock();
	duration=(double)(finish-start)/2000;       //平均运行时间
	printf("%f seconds\n",duration);

}

流程图
求最大公约数的4种常用算法是什么_用辗转相除法求最大公约数_https://bianchenghao6.com/blog__第1张
2.穷举法（也称枚举法）利用数学定义

穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。

定义1：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
定义2：对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。
代码：

#include<iostream>
using namespace std;
int divisor(int a,int b)         //自定义函数求两数的最大公约数
{ 
   
	int temp;
	temp=(a>b)?b:a;         //采用条件运算表达式求出两个数中的最小值
	while(temp>0)
	{ 
   
		if(a%temp==0&&b%temp==0)     //只要找到一个数能同时被a,b所整除，则中止循环
			break;
		temp--;                        //如不满足if条件则变量自减，直到能被a,b所整除
	}
	return(temp);                      //返回满足条件的数到主调函数处
}
int multiple(int a,int b)
{ 
   
	int p,q,temp;
	p=(a>b)?a:b;                     //求两个数中的最大值
	q=(a>b)?b:a;                     //求两个数中的最小值
	temp=p;                        //最大值赋给p为变量自增作准备
	while(1)                        //利用循环语句来求满足条件的数值
	{ 
   
		if(p%q==0)
			break;                  //只要找到变量的和数能被a或b所整除，则中止循环
		p+=temp;                   //如果条件不满足则变量自身相加
	}
	return(p);
}
int main()
{ 
   
	int m,n,t1,t2;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)
	{ 
   	
		printf("请重新输入正确整数：");
		cin.clear();                 //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=divisor(m,n);
	t2=multiple(m,n);
	printf("最大公因数为：%d\n",t1);
	printf("最小公倍数为：%d\n",t2);
	return 0;
}

测试及测试代码与平均运行时间：
测试代码：

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int divisor(int a,int b)
{ 
   
	int temp;
	temp=(a>b)?b:a;
	while(temp>0)
	{ 
   
		if(a%temp==0&&b%temp==0)
			break;
		temp--;
	}
	return(temp);
}
void main()
{ 
   
	int m[5000],n[5000],t1,i;
	clock_t start,finish;
    double duration;
	time_t t=time(NULL);
	srand(t);
	for(i=0;i<5000;i++)
	{ 
   
		m[i]=rand()%100;
		n[i]=rand()%100;
	}
	start=clock();
	for(i=0;i<5000;i++)
	{ 
   
		t1=divisor(m[i],n[i]);
		printf("%d %d %d\n",m[i],n[i],t1);
	}
	finish=clock();
	duration=(double)(finish-start)/5000;       //平均运行时间
	printf("%f seconds\n",duration);
}

流程图
求最大公约数的4种常用算法是什么_用辗转相除法求最大公约数_https://bianchenghao6.com/blog__第2张
3. 更相减损法

更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法>也叫等值算法。

代码：

#include<iostream>
#include<math.h>
using namespace std;
int gcd(int m,int n)                //求最大公约数
{ 
   
	int i=0,temp,x;
	while(m%2==0 && n%2==0)     //判断m和n能被多少个2整除(i个)
	{ 
   
		m/=2;
		n/=2;
		i+=1;
	}
	if(m<n)                       //m保存大的值
	{ 
   
		temp=m;
		m=n;
		n=temp;
	}
	while(x)
	{ 
   
		x=m-n;                     //{ 以较大的数减较小的数，
		m=(n>x)?n:x;             
		n=(n<x)?n:x;                //接着把所得的差与较小的数比较，
		if(n==(m-n))                //并以大数减小数。}
			break;
	}
	if(i==0)
		return n;
	else 
		return (int )pow(2,i)*n;
}
int main()
{ 
   
	int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)  //判断输入两数字是否小于零或为小数
	{ 
   	
		printf("请重新输入正确整数：");
		cin.clear();                        //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=gcd(m,n);
	printf("最大公因数为：%d\n",t1);
	printf("最小公倍数为：%d\n",m*n/t1);
	return 0;
}

测试及测试代码与平均运行时间：
测试代码：

#include<stdio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
int gcd(int m,int n)         //求最大公约数
{ 
   
	int i=0,temp,x;
	while(m%2==0 && n%2==0)  //判断m和n能被多少个2整除(i个)
	{ 
   
		m/=2;
		n/=2;
		i+=1;
	}
	if(m<n)     //m保存大的值
	{ 
   
		temp=m;
		m=n;
		n=temp;
	}
	while(x)
	{ 
   
		x=m-n;                     //{以较大的数减较小的数，
		m=(n>x)?n:x;               
		n=(n<x)?n:x;               //接着把所得的差与较小的数比较，
		if(n==(m-n))               //并以大数减小数。}
			break;
	}
	if(i==0)
		return n;
	else 
		return (int )pow(2,i)*n;
}
void main()
{ 
   
	int m[2000],n[2000],t1,i;
	clock_t start,finish;
	double duration;
	time_t t=time(NULL);
	srand(t);
	for(i=0;i<2000;i++)
	{ 
   
		m[i]=rand()%100;
		n[i]=rand()%100;
	}
	start=clock();
	for(i=0;i<2000;i++)
	{ 
   
		t1=gcd(m[i],n[i]);
		printf("%d %d %d\n",m[i],n[i],t1);
	}
	finish=clock();
	duration=(double)(finish-start)/2000;       //平均运行时间
	printf("%f seconds\n",duration);
}

流程图：
求最大公约数的4种常用算法是什么_用辗转相除法求最大公约数_https://bianchenghao6.com/blog__第3张
4.Stein算法

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。
试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。
那么一奇一个偶以及两个奇数的情况如何化小呢？
先来看看一奇一偶的情况： 设有2x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以 a = gcd( 2x,y ) 是奇数。
根据2x是个偶数不难联想到，a应该是x的约数。
我们来证明一下：
(2x)%a=0，设2x=na，因为a是奇数，2x是偶数，则必有n是偶数。
又因为 x=(n/2)*a，所以 x%a=0，即a是x的约数。
因为a也是y的约数，所以a是x和y的公约数，有 gcd( 2x,y ) <= gcd( x,y )。
因为gcd( x,y )明显是2x和y的公约数，又有gcd( x,y ) <= gcd( 2x,y )，
所以 gcd( 2x,y ) = gcd( x,y )。
至此，我们得出了一奇一偶时化小的方法。

再来看看两个奇数的情况：
设有两个奇数x和y，不妨设x>y，注意到x+y和x-y是两个偶数，
则有gcd( x+y,x-y ) = 2 * gcd( (x+y)/2,(x-y)/2 )，
那么 gcd( x,y ) 与 gcd( x+y,x-y ) 以及 gcd( (x+y)/2,(x-y)/2 ) 之间是不是有某种联系呢？
为了方便设 m=(x+y)/2 ，n=(x-y)/2 ，容易发现 m+n=x ，m-n=y 。
设 a = gcd( m,n )，则 m%a=0,n%a=0 ，
所以 (m+n)%a=0，(m-n)%a=0 ，即 x%a=0 ，y%a=0 ，
所以a是x和y的公约数，有 gcd( m,n )<= gcd(x,y)。
再设 b = gcd( x,y )肯定为奇数，则 x%b=0,y%b=0 ，
所以 (x+y)%b=0 ，(x-y)%b=0 ，
又因为x+y和x-y都是偶数，跟前面一奇一偶时证明a是x的约数的方法相同，
有 ((x+y)/2)%b=0,((x-y)/2)%b=0 ，即 m%b=0 ，n%b=0 ，
所以b是m和n的公约数，有 gcd( x,y ) <= gcd( m,n )。
所以 gcd( x,y ) = gcd( m,n ) = gcd( (x+y)/2,(x-y)/2 )。

*整理一下，对两个正整数 x>y ：
1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 )；
2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )；
2.x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
现在已经有了递归式，还需要再找出一个退化情况。注意到 gcd( x,x ) = x ，就用这个。

①函数非递归调用

#include<iostream>
using namespace std;
int Stein( unsigned int x, unsigned int y )         //函数非递归调用
{ 
        
    int factor = 0;                           //返回最大公约数x和y 
    int temp;
    if ( x < y )
	{ 
    
		temp = x;
		x = y;
		y = temp;
	}
	if ( 0 == y )
	{ 
   
		return 0;
	}
	while ( x != y )
	{ 
                                         //当x时偶数时 
		if ( x & 0x1 )
		{ 
   
			if ( y & 0x1 )
			{ 
                                  //当x和y都是偶数时 
				y = ( x - y ) >> 1;
				x -= y;
			}
			else
			{ 
                                   //当x是偶数，y是奇数 
				y >>= 1;
			}
		}
		else
		{ 
                                       //当x是奇数 
			if ( y & 0x1 )
			{ 
   
				x >>= 1;
				if ( x < y )
				{ 
   
					temp = x;
					x = y;
					y = temp;
				}
			}
			else
			{ 
                                   //当x和y都是奇数 
				x >>= 1;
				y >>= 1;
				++factor;
			}
	}
	}
	return ( x << factor );
}
int main()
{ 
   
	int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)        //判断输入两数字是否小于零或为小数
	{ 
   	
		printf("请重新输入正确整数：");
		cin.clear();                            //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=Stein(m,n);
	printf("最大公因数为：%d\n",t1);
	return 0;	
}

测试及测试代码与平均运行时间：
测试代码：

#include<stdio.h>
#include<time.h> 
#include<stdlib.h>
int Stein( unsigned int x, unsigned int y )
  /* return the greatest common divisor of x and y */
{ 
   
        int factor = 0;
        int temp;
        if ( x < y )
        { 
   
                temp = x;
                x = y;
                y = temp;
        }
        if ( 0 == y )
        { 
   
                return 0;
        }
        while ( x != y )
        { 
   
                if ( x & 0x1 )
                { 
   /* when x is odd */
                        if ( y & 0x1 )
                        { 
   /* when x and y are both odd */
                                y = ( x - y ) >> 1;
                                x -= y;
                        }
                        else
                        { 
   /* when x is odd and y is even */
                                y >>= 1;
                        }
                }
                else
                { 
   /* when x is even */
                        if ( y & 0x1 )
                        { 
   /* when x is even and y is odd */
                                x >>= 1;
                                if ( x < y )
                                { 
   
                                        temp = x;
                                        x = y;
                                        y = temp;
                                }
                        }
                        else
                        { 
   /* when x and y are both even */
                                x >>= 1;
                                y >>= 1;
                                ++factor;
                        }
                }
        }
        return ( x << factor );
}
void main()
{ 
   
	int m[2000],n[2000],t1,i;
	clock_t start,finish;
	double duration;
	time_t t=time(NULL);
	srand(t);
	for(i=0;i<2000;i++)
	{ 
   
		m[i]=rand()%100;
		n[i]=rand()%100;
	}
	start=clock();
	for(i=0;i<2000;i++)
	{ 
   
		t1=Stein(m[2000],n[2000]);
		printf("%d %d %d %d\n",m[i],n[i],t1);
	}
	finish=clock();
	duration=(double)(finish-start)/20000;       //平均运行时间
	printf("%f seconds\n",duration);

}

②函数递归调用

#include<iostream>
using namespace std;
int gcd(int u,int v)
{ 
   
    if (u == 0) return v;
    if (v == 0) return u;
                                       // 寻找两个数的最大公约数
    if (~u & 1)                        // u是偶数
    { 
   
        if (v & 1)                     // v是奇数
            return gcd(u >> 1, v);
        else                            // u和v都是偶数
            return gcd(u >> 1, v >> 1) << 1;
    }
     if (~v & 1)                         // u是奇数, v是偶数
        return gcd(u, v >> 1);
                                         // 减少较大的变量
    if (u > v)
        return gcd((u - v) >> 1, v);
     return gcd((v - u) >> 1, u);
}
int main()
{ 
   
	int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)     //判断输入两数字是否小于零或为小数
	{ 
   	
		printf("请重新输入正确整数：");
		cin.clear();                              //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=gcd(m,n);
	printf("最大公因数为：%d\n",t1);
	return 0;
}

测试及测试代码与平均运行时间：
测试代码：

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int gcd(int u,int v)
{ 
   
    if (u == 0) return v;
    if (v == 0) return u;
    if (~u & 1) 
    { 
   
        if (v & 1) 
            return gcd(u >> 1, v);
        else 
            return gcd(u >> 1, v >> 1) << 1;
    }
     if (~v & 1) 
        return gcd(u, v >> 1);
    if (u > v)
        return gcd((u - v) >> 1, v);
     return gcd((v - u) >> 1, u);
}
void main()
{ 
   
	int m[5000],n[5000],t1,i;
	clock_t start,finish;
	double duration;
	time_t t=time(NULL);
	srand(t);
	for(i=0;i<5000;i++)
	{ 
   
		m[i]=rand()%100;
		n[i]=rand()%100;
	}
	start=clock();
	for(i=0;i<5000;i++)
	{ 
   
		t1=gcd(m[i],n[i]);
		printf("%d %d %d\n",m[i],n[i],t1);
	}
	finish=clock();
	duration=(double)(finish-start)/5000;       //平均运行时间
	printf("%f seconds\n",duration);
}

流程图：
求最大公约数的4种常用算法是什么_用辗转相除法求最大公约数_https://bianchenghao6.com/blog__第4张

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。

上一篇

已是最后文章

下一篇

已是最新文章

发表回复

相关推荐

sql server2019自定义安装步骤_怎么安装office2019

linux php扩展安装_vue项目怎么跟php结合

windows系统的密码激活成功教程

SQL格式化_sql必知必会

最新文章

sql server2019自定义安装步骤_怎么安装office2019

4小时前 2

linux php扩展安装_vue项目怎么跟php结合

5小时前 1

windows系统的密码激活成功教程

5小时前 2

SQL格式化_sql必知必会

6小时前 2

nginx参数详解_nginx

6小时前 2

java多线程面试重点_java 面试 高质量 集合面试问题

7小时前 2

电脑插了网线没有网络_电脑插了网线没有网络

7小时前 2

qt绘制轨迹线_qt绘制轨迹线

8小时前 2

java实现二进制转十六进制的方法_16进制转换成2进制

8小时前 2

使用redis实现分布式锁及其优化_redis淘汰机制有几种

9小时前 2