c - 查找Array Code C语言的GCD

Question

我正在尝试用 C 编写一个程序。该程序应该找到给定数组的 GCD（最大公约数）。我正在尝试使用最小数量的数组来查找 GCD。我想知道我的最后一个循环有什么问题。我还没有想出一种方法来检查除法是否给出了任何小数点以停止循环。这是我的代码

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int A[10]={112, 160, 180, 240, 288, 32, 480, 96, 60, 72};
    int i;
    int j;
    int minimum = A[0];
    int GCD;
    int temp;

    for (i=1;i<9;i++)
    {
        if( A[i] < minimum)
        {
            minimum = A[i];
        }
    }

    for (i=1; i < minimum/2; i++)
    {
        for (j = 0; j < 9;j++)
        {
            GCD = 2*i;
            temp = ((A[j])/(GCD));
            int check = temp%1;
            if (check == 0)
                break;
        }
    }

    printf("The Greates Common Denominator is: %d", GCD);

    return 0;
}

Answer 1

#include <stdio.h>

unsigned gcd(unsigned x, unsigned y){
    unsigned wk;
    if(x<y){ wk=x;x=y;y=wk; }
    while(y){
        wk = x%y;
        x=y;
        y=wk;
    }
    return x;
}

int gcd_a(int n, int a[n]){
    if(n==1) return a[0];
    if(n==2) return gcd(a[0], a[1]);
    int h = n / 2;
    return gcd(gcd_a(h, &a[0]), gcd_a(n - h, &a[h]));
}

int main(void){
    int A[10]={112, 160, 180, 240, 288, 32, 480, 96, 60, 72};
    int size_A = sizeof(A)/sizeof(*A);
    int gcd = gcd_a(size_A, A);
    printf("%d\n", gcd);
    return 0;
}

Answer 2

#include <stdio.h>

static int gcd(int x, int y)
{
    int r;

    if (x <= 0 || y <= 0)
        return(0);

    while ((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return(y);
}

int main(void)
{
    int A[10] = { 112, 160, 180, 240, 288, 32, 480, 96, 60, 72 };
    int g = A[0];

    for (int i = 1; i < 10; i++)
        g = gcd(g, A[i]);

    printf("The Greatest Common Denominator is: %d\n", g);

    return 0;
}

答案是4。这显然是正确的；它是 32 和 60 的 GCD；其他的都可以被 4 整除。

如果需要，您可以使用以下方法优化循环：

    for (int i = 1; i < 10 && g != 1; i++)
        g = gcd(g, A[i]);

当 GCD 为1时，它不会变大，

Answer 3

#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b)
{
    int r;
    while(a)
    {
        r=b%a;
        b=a;
        a=r;
    }
    return b;
}
int gcd_(int* A, int N)
{
    int c=gcd(*A,*(A+1));
    int i,g;
    for(i=1;i<N-1;i++)
    {
        g=gcd(c,*(A+1+i));
        c=g;
    }
    return c;
}
int main(void)
{
    int A[]={96,60,32,72,84,90};
    int N=sizeof(A)/sizeof(A[0]);
    int t=gcd_(A,N);
    printf("%d",t);
    return 0;
}

Answer 4

 #include <iostream>
 using namespace std;

int gcd(int a, int b){
int t;
while(a)
{
    t = a;
    a = b%a;
    b = t;
}
return b;
}

int main(){
int n;
cout<<"how many numbers (Max 10): "; // your choice
cin>>n;
cin.ignore();
cout<<endl;
int arr[n-1];

for (int i = 0; i < n; ++i) {

  cin>>arr[i];

}
int ans;

ans = arr[0];
for (int j = 0; j < n; ++j) {
    ans = gcd(ans,arr[j]);
}
cout<<"GCD = "<<ans;


//cin.get();
return 0;
}

Answer 5

  #include <stdio.h>
  #include <stdlib.h>

  int main() {
        int i, j, n, flag = 0, small, *data;

        /* get the number of inputs from the user */
        printf("Enter the number of inputs:");
        scanf("%d", &n);

        /* allocate memory to store n numbers */
        data = (int *)malloc(sizeof(int) * n);

        /* get n numbers from the user */
        for (i = 0; i < n; i++) {
                printf("Data[%d]: ", i);
                scanf("%d", &data[i]);
        }

        /* find the smallest of n numbers */
        small = data[0];
        for (i = 1; i < n; i++) {
                if (data[i] < small)
                        small = data[i];
        }

        /*
         * use the smallest no to find gcd of n numbers.
         * Start checking from small to 1 whether the 
         * same value divides all the given inputs
         */
        for (i = small; i > 0; i--) {
                for (j = 0; j < n; j++) {
                        if (data[j] % i != 0) {
                                flag = 1;
                        }
                }
                /* print the result */
                if (!flag) {
                        printf("GCD of given %d numbers is %d\n", n, i);
                        break;
                }
                flag = 0;
        }

        return 0;
  }

Answer 6

#include <stdio.h>
#include <conio.h>

int x;

void main()
{
  int i,num[10]={0};
  printf("How many numbers do you want to enter =");
  scanf("%d",&x);
  for(i=0;i<x;i++)
  scanf("%d",& num[i]);
  printf("The hcf of the numbers are = %d ", hcf(num));

 }

 int hcf(int num[])
 {
   int count,rem,lv,i,j;
   lv=gnum(num);
   if(lv==1)
     return 1;

 for(j=2;j<=lv;j++)
 {
       count =0;

        for(i=0;i<x;i++)
     {
         rem = num[i]%j ;

         if( rem != 0 || num[i]< j )
          break;

         else
           {
             count++;
           }

    }

    if(count == x)
        {
         for(i=0;i<x;i++)
          num[i]=num[i]/j;
          return(j*hcf(num));
        }


 }

 if(count!= x)
    return 1;

}

  int  gnum(int num[])
 {
    int i,temp=num[0];
      for(i=0;i<x;i++)
    {
      if(temp >= num[i])
      temp = num[i];
    }

     return (temp);
 }

Answer 7

#include <stdio.h>
#include<stdlib.h>

int main(void)
 {
int A[2] = {10,30};
int a,b,r,i;
for ( i = 1; i < 2; i++)
{
 a=A[0],b=A[i];
  while(b!=0)
  {

   r=a%b;/*remainder*/
   a=b;
   b=r;
 }
}
printf("The Greatest Common Denominator is: %d\n", a);
return 0;

}

/*You can change the **for** loop range according to the array values*\

Answer 8

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int A[10]={112, 160, 180, 240, 288, 32, 480, 96, 60, 72};
    int i;
    int j;
    int minimum = A[0];
    int GCD;
    int temp;
    int f;
    for (i=1;i<10;i++)
    {
        if( A[i] < minimum)
        {
            minimum = A[i];
        }
    }

    for (i=1; i <= minimum; i++)
    {
        f=0;
        for (j = 0; j < 10;j++)
        {

            if(A[j]%i!=0)
            {
               f=1; 
               break;
            }



        }
        if(f==0)
         GCD=i;
    }

    printf("The Greates Common Denominator is: %d ", GCD);

    return 0;
}

    enter code here