a=g_cd(m,n);

if (m>n) //最小公倍數(shù)=較大的數(shù)*(較小的數(shù)/最大公約數(shù))

{

b=n;

b/=a;

return m*b;

}

else

{

b=m;

b/=a;

return n*b;

}

}

main()

{

int p,r,n,m,temp;

printf("Please enter 2 numbers n,m:");

scanf("%d,%d",&n,&m);//輸入兩個正整數(shù).

if(n

在m中.

{temp=n;

n=m;

m=temp;

}

p=n*m;//P是原來兩個數(shù)n,m的乘積.

while(m!=0)//求兩個數(shù)n,m的最大公約數(shù).

{

r=n%m;

n=m;

m=r;

}

printf("Its MAXGongYueShu:%d\n",n);//打印最大公約數(shù).

printf("Its MINGongBeiShu:%d\n",p/n);打印最小公倍數(shù).

基本原理如下：

用歐幾里德算法(輾轉(zhuǎn)相除法)求兩個數(shù)的最大公約數(shù)的步驟如下：

先用小的一個數(shù)除大的一個數(shù)，得第一個余數(shù)；

再用第一個余數(shù)除小的一個數(shù)，得第二個余數(shù)；

又用第二個余數(shù)除第一個余數(shù)，得第三個余數(shù)；

這樣逐次用后一個數(shù)去除前一個余數(shù)，直到余數(shù)是0為止。那么，最后一個除數(shù)就是所求的最大公約數(shù)(如果最后的除數(shù)是1，那么原來的兩個數(shù)是互質(zhì)數(shù))。

例如求1515和600的最大公約數(shù)，

第一次：用600除1515，商2余315；

第二次：用315除600，商1余285；

第三次：用285除315，商1余30；

第四次：用30除285，商9余15；

第五次：用15除30，商2余0。

1515和600的最大公約數(shù)是15。

兩個正整數(shù)的最小公倍數(shù)=兩個數(shù)的乘積÷兩個數(shù)的最大公約數(shù)

由于兩個數(shù)的乘積等于這兩個數(shù)的最大公約數(shù)與最小公倍數(shù)的積。這就是說，求兩個數(shù)的最小公倍數(shù)，可以先求出兩個數(shù)的最大公約數(shù)，再用這兩個數(shù)的最大公約數(shù)去除這兩個數(shù)的積，所得的商就是兩個數(shù)的最小公倍數(shù)。

例 求105和42的最小公倍數(shù)。

因為105和42的最大公約數(shù)是21，

105和42的積是4410，4410÷21＝210，

所以，105和42的最小公倍數(shù)是210。

#include

void main()

{

int i,j,k;

long m;

printf("please input i,j:\n");

scanf("%d%d",&i,&j);

m=i*j;

if(i

{i=i^j;

j=j^i;

i=i^j;}

while(i%j!=0)

{k=i%j;

i=j;

j=k;}

printf("gcd=%d,lcm=%ld\n",j,m/j);

}

給，已經(jīng)編譯運行確認：

#include

#include

int main()

{

int p,r,n,m,temp;

printf("Please enter 2 numbers n,m:");

scanf("%d %d",&n,&m);//輸入兩個正整數(shù).

if(n

{

temp=n;

n=m;

m=temp;

}

p=n*m;//P是原來兩個數(shù)n,m的乘積.

while(m!=0)//求兩個數(shù)n,m的最大公約數(shù).

{

r=n%m;

n=m;

m=r;

}

printf("最大公約數(shù)為: %d\n",n);//打印最大公約數(shù).

printf("最小公倍數(shù)為: %d\n&qu

總結(jié)

以上是生活随笔為你收集整理的用c语言求最大公约数的流程图,如何用c语言求最大公约数和最小公倍数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。