求多个数的最大公约数！！（请高手指教！！！）

ly4885806

最近在论坛上看到关于多个数最大公约数的求法，大家见解不一。我没事也做了一个，自我感觉良好。不知道我的算不算是一种新的解法（本人至今未看到过，可能见识短浅吧！）。希望高手能够指点一二。如果您有空，请把更妙的解法写下来，也让我们这些菜鸟见识一下世面。谢谢！！！
如果想赞的，请不要客气，尽情发挥。
如果想骂的，请含蓄点。

1. 
   
2. #include<stdio.h>
   
3. #define N 4
   
4. int min(int a[]);
   
5. int chan(int a[]);
   
6. void main()
   
7. {
   
8.         int a[N],i,j,t,p[N],q;
   
9.         for(i=0;i<N;i++)
   
10.                 scanf("%d",a+i);
    
11.         t=min(a);
    
12.         for(j=t;j>1;j--)
    
13.         {
    
14.                 for(i=0;i<N;i++)
    
15.         p[i]=a[i]%j;
    
16.         q=chan(p);
    
17.         if(q)
    
18.                 {
    
19.                         printf("成功，最大公约数为：%d\n",j);
    
20.                         break;
    
21.                 }
    
22.         }
    
23.         if(j==1)  printf("不存在最大公约数");
    
24. }
    
25. int min(int a[])
    
26. {
    
27.         int i;
    
28.         for(i=0;i<N;i++)
    
29.                 if(*a>*(a+i))   *a=*(a+i);
    
30.                 return *a;
    
31. }
    
32. int chan(int a[])
    
33. {
    
34.         int i;
    
35.         for(i=0;i<N;i++)
    
36.                 if(a[i]!=0)  return 0;
    
37.                 return 1;
    
38. }
    

复制代码

圆点坐标

没意思

dbcat

不错,如果有算法的说明就更好了!

dbcat

帮你改了一下,见笑了:

1. 
   
2. #include<stdio.h>
   
3. 
   
4. int min(int *,int );
   
5. int chan(int *,int);
   
6. 
   
7. main()
   
8. {
   
9.         int *a,i,j,t,*p,q,N;
   
10.         scanf("%d",&N);
    
11.         puts("\n");
    
12.         a=(int *) malloc (N*sizeof(int));
    
13.         p=(int *) malloc (N*sizeof(int));
    
14.         for(i=0;i<N;i++)
    
15.                 scanf("%d",a+i);
    
16.         t=min(a,N);
    
17.         for(j=t;j>1;j--)
    
18.         {
    
19.                 for(i=0;i<N;i++)
    
20.         p[i]=a[i]%j;
    
21.         q=chan(p,N);
    
22.         if(q)
    
23.                 {
    
24.                         printf("成功，最大公约数为：%d\n",j);
    
25.                         break;
    
26.                 }
    
27.         }
    
28.         if(j==1)  printf("不存在最大公约数");
    
29. 
    
30. }
    
31. int min(int a[],int N)
    
32. {
    
33.         int i;
    
34.         for(i=0;i<N;i++)
    
35.                 if(*a>*(a+i))   *a=*(a+i);
    
36.                 return *a;
    
37. }
    
38. int chan(int a[],int N)
    
39. {
    
40.         int i;
    
41.         for(i=0;i<N;i++)
    
42.                 if(a[i]!=0)  return 0;
    
43.                 return 1;
    
44. }

复制代码

win_hate

原帖由 ly4885806 于 2005-12-28 19:30 发表
                  break;
                }
        }
        if(j==1)  printf("不存在最大公约数");
}

不存在，这个......

hisher

如果我要求10000和9999的最大公约数那不是要循环判断9999次。。。。。

ly4885806

呵呵 我的程序做的确实不怎么样  有等改进。
谢谢4楼帮我改了一下，长了见识。
大家有意见尽管提呀~~~

ly4885806

楼主：请大家注意上面的两个程序都是错误的，至于错在哪我还没看出来，请高手指点一下。

soul_of_moon

当然不需要,只需判断2到min(a,b)的平方数之间的素数即可.俺没看楼主的代码.

frog_skywalker

用辗转相除法吧
纯搜索几个大的素数乘出来的数求起来比较费事