最小公约数函数名称c语言 最小公约数计算c语言

C语言中 用函数调用求最大公约数和最小公倍数

#includestdio.h

创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于做网站、成都网站制作、山丹网络推广、成都小程序开发、山丹网络营销、山丹企业策划、山丹品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供山丹建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

int gcd(int m, int n);

int lcd(int m, int n);

int main()

{

int a, b;

printf("输入两个正整数:");

scanf("%d%d", a, b);

printf("%d 和 %d 最大公约数为%d\n", a, b, gcd(a, b));

printf("最小公倍数为:%d\n", lcd(a, b));

}

int gcd(int m, int n)

{

int t;

if (mn)

{

t = m;

m = n;

n = t;

}

while (n != 0)

{

t = m%n;

m = n;

n = t;

}

return m;

}

int lcd(int m, int n)

{

int t;

t = m*n / gcd(m, n);

return t;

}

C语言用函数求最大公约，最小公约数

#includestdio.h

int main()

{

int zdgys(int x, int y); //求最大公约数

int zxgbs(int x, int y); //求最小公倍数

int a,b,max,min;

scanf("%d %d",a,b);

max = zdgys(a, b); //求最大公约数

min = zxgbs(a, b); //求最小公倍数

printf("最大公约数为%d，最小公倍数为%d",max,min);

return 0;

}

int zdgys(int x, int y)

{

int i,r,t=xy ? x : y;

for (i=1;i=t;i++)

{

if (x%i == 0 y%i == 0)

r=i;

}

return r;

}

int zxgbs(int x, int y)

{

int i,t=xy ? x : y;

for (i = t;;)

{

if (i%x == 0 i%y == 0)

break;

else

i++;

}

return i;

}

c语言如何求最大公约数和最小公倍数

#include stdio.h

int main()

{

int a,b,c,m,t;

printf("请输入两个数:\n");

scanf("%d%d",a,b);

if(ab)

{

t=a;

a=b;

b=t;

}

m=a*b;

c=a%b;

while(c!=0)

{

a=b;

b=c;

c=a%b;

}

printf("最大公约数是:\n%d\n",b);

printf("最小公倍数是:\n%d\n",m/b);

}

扩展资料

算法思想

利用格式输入语句将输入的两个数分别赋给 a 和 b，然后判断 a 和 b 的关系，如果 a 小于 b，则利用中间变量 t 将其互换。

再利用辗转相除法求出最大公约数，进而求出最小公倍数。最后用格式输出语句将其输出。

#includestdio.h是在程序编译之前要处理的内容，称为编译预处理命令。编译预处理命令还有很多，它们都以“#”开头，并且不用分号结尾，所以是c语言的程序语句。

求最小公约数c语言

没有“最小公约数”，只有“最小公倍数”。

最大公约数：

指两个或多个整数共有约数中最大的一个。

最小公倍数：

指两个或多个整数公有的倍数中最小的一个，另外，公约数，亦称“公因数”。它是一个能被若干个整数同时均整除的整数。”

C语言4种常见算法：

//C语言实现 四种方法求最大公约数

// 2019 03

// WANTING WANG

#includestdio.h

#includestdlib.h

#includetime.h

#includemath.h

//辗转相除法

int gcd(int a,int b)

{

if(a%b==0)

return b;

else;

return gcd(b,a%b);

}

//穷举法

int divisor (int a, int b) //自定义函数求两数的最大公约数

{

int  temp;//定义整型变量

temp=(ab)?b:a;//采种条件运算表达式求出两个数中的最小值

while(temp0)

{

if(a%temp==0b%temp==0)//只要找到一个数能同时被a,b所整除，则中止循环

break;

temp--;//如不满足if条件则变量自减，直到能被a,b所整除

}

return (temp);//返回满足条件的数到主调函数处

}

//更相减损法

int gcd2(int m,int n)

{

int i=0,temp,x;

while(m%2==0n%2==0)//判断m和n能被多少个2整除

{

m/=2;

n/=2;

i+=1;

}

if(mn)//m保存大的值

{

temp=m;

m=n;

n=temp;

}

while(x)

{

x=m-n;

m=(nx)?n:x;

n=(nx)?n:x;

if(n==(m-n))

break;

}

if(i==0)

return n;

else

return (int) pow(2,i)*n;

}

//Stein算法

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 );

}

int main()

{

int i;

int a[30];

for(i=0;i30;i++)

{

a[i]=rand()%100 + 1;

printf("%d ",a[i]);

}

printf("\n");

int b[30];

for(i=0;i30;i++)

{

b[i]=rand()%100 + 1;

printf("%d ",b[i]);

}

printf("\n");

clock_t start,finish;

double dur;

start= clock();

for(i=0;i30;i++)

{

//printf("辗转相除法所得最大公约数为：%d\n",gcd(a[i],b[i]));

//printf("穷举法所得最大公约数为：%d\n",divisor(a[i],b[i]));

printf("更相减损法所得最大公约数为：%d\n",gcd2(a[i],b[i]));

//printf("Stein算法所得最大公约数为：%d\n",Stein(a[i],b[i]));

}

finish=clock();

dur=(double)(finish-start)/CLOCKS_PER_SEC;

printf("运行所用的时间为：%lf s\n",dur);

return 0;

}