首页 > 代码库 > 关于gcd函数解最大公约数
关于gcd函数解最大公约数
数学知识:由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积.即(a,b)×[a,b]=a×b.所以,求两个数的最小公倍数,就可以先求出它们的最大公约数,然后用上述公式求出它们的最小公倍数.
例如,求[18,20],即得[18,20]=18×20÷(18,20)=18×20÷2=180.
求几个自然数的最小公倍数,可以先求出其中两个数的最小公倍数,再求这个最小公倍数与第三个数的最小公倍数,依次求下去,直到最后一个为止.最后所得的那个最小公倍数,就是所求的几个数的最小公倍数.
编程知识:
int gcd(int a,int b){ //声明函数
if (b==0) return a;
else return gcd(b,a%b);}
下面是完整算法: 下面是写法:
int gcd(int a,int b) # include<stdio.h>
{ int gcd(int a,int b)
int c,r; {if(b==0) return a;
if(a<b){c=a;a=b;b=c;} else return gcd(b,a%b);}
r=a%b; int main
while(r) {}
{
a=b;b=r;r=a%b;
}
return b;
}
下面是用法:
gcd(x,y) 表示x和y的最大公约数
关于gcd函数解最大公约数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。