求最大公约数的两种解法(欧几里得算法和素数分解)
最大公约数的两种解法(欧几里得算法和素数分解)
方法一: 欧几里得算法,又称辗转相除法
定理(欧几里得算法):设a和b是正整数,则存在最大求最大公因子d=(a,b)的一种算法,且存在求一组整数s,t使得d = sa+tb
举个例子:求168和60的最大公约数?
168 = 2 * 60 + 48
60 = 1 * 48 +12
48 = 4 * 12
由此得最大公约数为12
关于最大公倍数
C语言程序代码:很简单就不加注释了
#include<stdio.h> #define SWAP(a,b) {a=a+b; b=a-b; a=a-b; } int gcd(int a,int b) { if(a==b) return a; if(a<b) SWAP(a,b); int temp = 0; while(a%b) { temp = b; b = a % b; a = temp; } return b; } int main() { int a = 168; int b = 60; printf("最大公约数是: %d\n",gcd(a,b)); return 0; }
方法二:素数分解
我们知道每一个大于等于2的整数都可以表示为几个素数相乘的形式(算术基本定理)而且有其对应的唯一的分解式,利用这点我们也可以用来求解最大公因子(最大公约数)
例如:在上题中168 可以表示为pow(2,3)*pow(3,1)*pow(5,0)*pow(7,1)
60可以表示为pow(2,2)*pow(3,1)*pow(5,1)*pow(7,0)
所以(168,60) = pow*(2,2)*pow(3,1)*pow(5,0)*pow(7,0) = 12
#include<stdio.h> #include<math.h> #define COUNT_PRIME 10 void Divisor(int num,int prime[],int index,int& loop)//求分解的因子的个数 { if(num==1) return; int count = 0; while(num%index==0) { num /= index; count++; } if(index==2) { prime[index-2] = count; index += 1; } else { prime[index/2] = count; index += 2; } Divisor(num,prime,index,loop); loop += 1; } int Gcd(int a[],int b[],int loop_a,int loop_b)//求解最大公因子 { int gcd = a[0]<b[0]?pow(2,a[0]):pow(2,b[0]); for(int i=1,j=3;i<loop_a||i<loop_b;i++,j+=2) { int num = a[i]<b[i]?pow(j,a[i]):pow(j,b[i]); gcd *= num; } return gcd; } int main() { int a = 60,b = 168; int prime_a[COUNT_PRIME] = {0}; int prime_b[COUNT_PRIME] = {0}; int loop_a = 0,loop_b = 0; Divisor(a,prime_a,2,loop_a); Divisor(b,prime_b,2,loop_b); int gcd = Gcd(prime_a,prime_b,loop_a,loop_b); printf("最大公约数是: %d\n",gcd); printf("最大公倍数是: %d\n",a*b/gcd); return 0; }
这里主要的函数在于求各个因子的个数,我使用了递归来解决这个问题
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。