Question

如何使用辗转相除法求其最大公约数和最小公倍数?

Answer 1

/*这个程序是我帮别人写的最后没有，先求a b c 的最大公约数yue 再求
d e f 的公倍数bei 然后求即是yue的倍数又是bei的约数的数，里面有公约数和
公倍数的求法你可以参照下 */
#include"stdio.h"
main()
{
int a,b,c,d,e,f,i;
int max,yue=1,beie=1,beif=1,bei=1;
printf("input a b c d e f:\n");
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
max=a;
if(max<b)
max=b;
if(max<c)
max=c;

for(i=max;i>=2;i--)

if(a%i==0&&b%i==0&&c%i==0)
{
yue=yue*i;
a=a/i;
b=b/i;
c=c/i;
}

for(i=max;i>=2;i--)
{
if(e%i==0&&d%i==0)
{
beie*=i;
e=e/i;
d=d/i;
}
}
beie=beie*e*d;
for(i=max;i>=2;i--)
if(e%i==0&&f%i==0)
{
beif*=i;
e=e/i;
f=f/i;
}

beif=beif*e*f;

for(i=beie;i>=2;i--)
if(beie%i==0&&beif%i==0)
{
bei*=i;
beie=beie/i;
beif=beif/i;
}

bei=bei*beie*beif;
printf("%d\n",bei);
for(i=yue;i<=bei;i++)
if(i%yue==0&&bei%i==0)
printf("%d\n",i);

}

Answer 2

举几个例子：
12_8
___8_4 - 能整除，最大公约数4

92_24
___24_20
______20_4 - 能整除，最大公约数4

a_b
__b_a%b (a=a%b;swap(a,b);)

Answer 3

"/*这个程序是我帮他人写的最后木有，先求a
b
c
的最大公约数yue
再求
d
e
f
的公倍数bei
之后求即是yue的倍数又是bei的约数的数，里边有公约数和
公倍数的求法你可以参照下
*/
#include"stdio.h"
main()
{
int
a,b,c,d,e,f,i;
int
max,yue=1,beie=1,beif=1,bei=1;
printf("input
a
b
c
d
e
f:\n");
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
max=a;
if(max<b)
max=b;
if(max<c)
max=c;
for(i=max;i>=2;i--)
if(a%i==0&&b%i==0&&c%i==0)
{
yue=yue*i;
a=a/i;
b=b/i;
c=c/i;
}
for(i=max;i>=2;i--)
{
if(e%i==0&&d%i==0)
{
beie*=i;
e=e/i;
d=d/i;
}
}
beie=beie*e*d;
for(i=max;i>=2;i--)
if(e%i==0&&f%i==0)
{
beif*=i;
e=e/i;
f=f/i;
}
beif=beif*e*f;
for(i=beie;i>=2;i--)
if(beie%i==0&&beif%i==0)
{
bei*=i;
beie=beie/i;
beif=beif/i;
}
bei=bei*beie*beif;
printf("%d\n",bei);
for(i=yue;i<=bei;i++)
if(i%yue==0&&bei%i==0)
printf("%d\n",i);
}"

Answer 4

/*这个程序是我帮别人写的最后没有，先求a
b
c
的最大公约数yue
再求
d
e
f
的公倍数bei
然后求即是yue的倍数又是bei的约数的数，里面有公约数和
公倍数的求法你可以参照下
*/
#include"stdio.h"
main()
{
int
a,b,c,d,e,f,i;
int
max,yue=1,beie=1,beif=1,bei=1;
printf("input
a
b
c
d
e
f:\n");
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
max=a;
if(max<b)
max=b;
if(max<c)
max=c;
for(i=max;i>=2;i--)
if(a%i==0&&b%i==0&&c%i==0)
{
yue=yue*i;
a=a/i;
b=b/i;
c=c/i;
}
for(i=max;i>=2;i--)
{
if(e%i==0&&d%i==0)
{
beie*=i;
e=e/i;
d=d/i;
}
}
beie=beie*e*d;
for(i=max;i>=2;i--)
if(e%i==0&&f%i==0)
{
beif*=i;
e=e/i;
f=f/i;
}
beif=beif*e*f;
for(i=beie;i>=2;i--)
if(beie%i==0&&beif%i==0)
{
bei*=i;
beie=beie/i;
beif=beif/i;
}
bei=bei*beie*beif;
printf("%d\n",bei);
for(i=yue;i<=bei;i++)
if(i%yue==0&&bei%i==0)
printf("%d\n",i);
}