C语言经典案例:输入两个正整数m和n,求其最大公约数和最小公倍
需求描写:输出两个正整数m和n,求其最至公约数和最小公倍数。
C语言案例剖析:
(1)最小公倍数=输出的两个数之积除于它们的最至公约数,症结是求出最至公约数;
(2)求最至公约数用展转相除法(别名欧几里德算法)
1)证实:设c是a和b的最至公约数,记为c=gcd(a,b),a>=b,
令r=a mod b
设a=kc,b=jc,则k,j互素,不然c不是最至公约数
据上,r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍数,且k-mj与j互素,不然与前述k,j互素抵触,
由此可知,b与r的最至公约数也是c,即gcd(a,b)=gcd(b,a mod b),得证。
2)算法描写:
第一步:a ÷ b,令r为所得余数(0≤r
第二步:交换:置 a←b,b←r,并前往第一步。
实现代码如下:
#include<stdio.h>
int main()
{
int a,b,t,r,n;
printf("请输出两个数字:\n");
scanf("%d %d",&a,&b);
if(a<b)
{t=b;b=a;a=t;}
r=a%b;
n=a*b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
printf("这两个数的最至公约数是%d,最小公倍数是%d\n",b,n/b);
return 0;
}
本案例运行效果如下:
请输出两个数字:
12 26
这两个数的最至公约数是2,最小公倍数是156
本文由IT教学网整理发布,转载请注明出处:http://www.itjx.com/jiaocheng/cyuyan/1051.html