公约数和公倍数的问题,决不是作业!!!

fydream

再次强调这不是作业,只是我的爱好!!
题目是:输入两个正整数,求其最大公约数和最小公倍数.
我只写出一小断代码:
main()
{
long m,n,i;
scanf("%ld,%ld",&m,&n);
if(m==n)
  {printf("the gong yue shu is");printf("%ld\n",m);
   printf("the gong bei shu is");printf("%ld",m);
  }
  else if ...............
后面的算法我实在是想不出来,请各位兄弟,帮忙给个思路,"JUST 思路"
我不要代码.人格保证绝对不是家庭作业!!!谢谢了!

HOUSCOUS

Use the prime fatorizations of these intergers.

firemoth

fatorization?我想应该是factorization吧

fydream

能不能说中文!我外语不是很好!谢谢!

yueyemingming

公约数是两个数中约数的公共部分，其较简单的算法是：
假如使用data1,data2为例：
从2开始到data1平方根范围内的所有data1的约数a
去乘
从data1除以2开始到data2范围内的所有数b
这个过程中，如果存在a乘以b得到data2
那么a就是他们的公约数了，而他们的公倍数就是a乘已data1;
算法应该没问题！试试吧！
看看我的资料，与我联系！

fydream

为“求最大公约数与最小公倍数”开辟新径



——数学教学中的一点心得


　


瓦房店市复州湾中心小学 迟栋


　



求最大公约数与最小公倍数在小学阶段是一个非常重要的教学内容。它们是约分和通分的第一步，是关键的第一步，正所为“一招走错，满盘皆输”。准确迅速地求出最大公约数与最小公倍数就为约分和通分铺平了前进的道路，也为进行分数计算奠定了坚实的基础。


在教学最大公约数和最小公倍数时，我除了教会学生教材中的用短除法分解质因数的方法外，又教给学生另外几种方法，为求最大公约数和最小公倍数开辟了一条新径。


心得一：求两个数的最小公倍数，可先用较大的数乘1，看积能否被较小的数整除。能，则该积是它们的最小公倍数，若不能则积就不是它们的最小公倍数；再用较大的数乘以2，看积能否被较小的数整除，若能则积是，若不能积则不是；以此类推，直至求出这两个数的最小公倍数为止。例如：8和10，10×1÷8，10×2÷8，10×3÷8都不符合整除条件，所以10，20，30都不是10和8的最小公倍数。10×4÷8符合整除条件，所以10×4＝40是它们的最小公倍数。以上可简述成：较大数依次乘以自然数，再除以较小数，能求出最小公倍数。


心得二：求最大公约数，可先用较小的数依次除以1，2，3，4等自然数，用所得的商去除较大的数，如果两次都能整除，则第一步所得的商就是它们的最大公约数，否则就不是。如10和8，10÷(8÷1)，10÷(8÷2)，10÷(8÷3)，这些都不符合上述条件，因而8÷1，8÷2，8÷3都不是10和8 的最大公约数，而当8÷4＝2，10÷2＝5时，符合了上述条件，所以8÷4才是10和8的最大公约数。以上可简述成： 较小数依次除以自然数，再去除较大数，能求出最大公约数。


心得三：检验最大公约数和最小公倍数是否正确，可用定义法检验就行了。但如果同时求出了两个数的最大公约数和最小公倍数，还有另外一种可同时检验两者是否正确的方法，即采用下列公式：最大公约数×最小公倍数＝这两个数的乘积。如：求出10和8 的最大约数是2，最小公倍数是40，2×40＝10×8，两式相等说明求出的最大公约数和最小公倍数是正确的，否则错误。


以上心得，它不仅能够帮助学生更透彻地掌握所学的内容，而且拓宽了学生解题的思路，丰富了书本上的知识；它不仅使学生可自由选择解法，灵活运用，更重要的是还能提高分数计算的速度。

fydream

好的谢谢你们!

HOUSCOUS

[quote:d2e4e9103b="firemoth"]fatorization?我想应该是factorization吧[/quote]

Yes, mine was a mistyped.

fydream

我的代码：
#include <stdio.h>
#include <math.h>
main()
{
long m,n,a,b,i;
scanf("%ld,%ld",&m,&n);
i=(long)sqrt(m);
b=m/2;
loop: for(a=2,b=m/2;a<i,b<n;a++,b++)
     {if(a*b==n)
      {printf("gongyue ");printf("%ld\n",a);
       printf("gongbei ");printf("%ld",a*m);
      }
      else goto loop;
     }
}   

这是编译结果：
[root@fydream yuandaima]# gcc -o fydream 6.c
/tmp/ccuvVu14.o(.text+0x36): In function `main':
: undefined reference to `sqrt'
collect2: ld returned 1 exit status
然后我还以为是我用“SQRT”是应该给变量一个类型呢，然后我就在第七行改了一下：这是我改后的第七行：i=(long)sqrt(m);
但是编译结果变成：
[root@fydream yuandaima]# gcc -o fydream 6.c
6.c: In function `main':
6.c:7: error: syntax error before "long"
能告诉我是怎么回事么？：）谢谢了！：）

fydream

不知道这个算法怎么样？和YUEYEMINGMING老兄的算法差不多，只是有一点不同！：）
这个是算法：
求两个正整数m和n的最大公约数。
　　分析：求两个正整数的最大公约数采用的辗转相除法求解。以下是辗转的算法：
　　分别用m,n,r表示被除数、除数、余数。
　　①求m/n的余数r.
　　②若r=0,则n为最大公约数.若r≠0,执行第③步.
　　③将n的值放在m中,将r的值放在n中.
　　④返回重新执行第①步。

sagaeon

要链接数学库 -lm

Axin

我面试的时候也遇到过这样的题目，我的想法是这样的：

int A，B，C，D，E；

先判断定A>B，C=A-B;

如果C>B，则B<=>C //如果C大于B，则B与C交换

D=B/C；

E=B-C*D；//E为最大公约数，这个地方还要判断如果为0，则E=C

不清楚有没有不健全的地方，如果是对的，这个算法没有循环，比较简洁。
[code:1]int main()
{
        int a,b,c,d,e,f;
        scanf("%d,%d",&a,&b);
        if (b>a)
                {
                        f=a;
                        a=b;
                        b=f;
                }

        c=a-b;
        if (c>b)
                {
                        f=b;
                        b=c;
                        c=f;
                }

                d=b/c;
                e=b-c*d;
                if (e==0)
                        e=c;
                if (a%e!=0)
                        e=1;
        printf("result=%d",e);
        return 0;
}
[/code:1]

fydream

谢谢楼上得兄弟!!
我按照我在网上找的算法写了一个虽然编译通过了！但是情看：
/*求两个正整数m和n的最大公约数。
分析：求两个正整数的最大公约数采用的辗转相除法求解。以下是辗转的算法：
分别用m,n,r表示被除数、除数、余数。
①求m/n的余数r.
②若r=0,则n为最大公约数.若r≠0,执行第③步.
③将n的值放在m中,将r的值放在n中.
④返回重新执行第①步。*/
#include <math.h>
main()
{
long m,n,r;
scanf("%d %d\n",&m,&n);
if(m>n) r=m%n;
else if(m<n) r=n%m;
     else {printf("gongyue ");printf("%d",n);}
      while(r!=0)
      {
       m=n;n=r;
      }
if(r=0) printf("%d",n);
}
编译：
[fydream@fydream yuandaima]$ gcc -lm -o fy gong.c
[fydream@fydream yuandaima]$ ./fy
5 3

应该在上一行显示“1”呀，但是什么都没有显示 。。。
请指教！：）谢谢了！：）

fydream

AXIN老兄!你的代码拾绝对正确的!我验证了!太谢谢你了!但是我觉得这样的题,我一般还是回现考虑用循环作!太谢谢你了!

lovewilliam

[code:1] while(r!=0)
{
m=n;n=r;
} [/code:1]

死循环

Axin的代码还是比较好的