求最大公约数的两种解法（欧几里得算法和素数分解）

理解并运用基础的数学公式和计算方法 #生活技巧# #工作学习技巧# #数字技能提升#

最大公约数的两种解法（欧几里得算法和素数分解）

方法一： 欧几里得算法，又称辗转相除法

定理（欧几里得算法）：设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;

}

这里主要的函数在于求各个因子的个数，我使用了递归来解决这个问题

网址：求最大公约数的两种解法（欧几里得算法和素数分解） https://www.yuejiaxmz.com/news/view/501409

相关内容

“绿色家电”成IFA最大公约数，AI能否缓解欧洲能源危机？
Matlab使用节约里程法(CW)方法进行VRP的求解
节约里程法—单配送中心CVRP求解
节约里程法求解CVRP问题
【案例】数据挖掘与生活：算法分类和应用
数据 + 进化算法 = 数据驱动的进化优化？进化算法 PK 数学优化
求解数据中心节能：东数如何“细”算？
【学法指导】用数轴法解一类化学计算题
使用蛮力法求解数字迷问题（类似ABCAB*A = DDDDDD）
《中华人民共和国数据安全法》十大法律要点解析

随便看看