Finding GCD of Array Code C language

StackOverflow https://stackoverflow.com/questions/21128981

Question

I am trying to write a program in C. The program is supposed to find the GCD (greatest common divisor) of a given array. I am trying to use the smallest number of the array to find the GCD. I was wondering whats wrong with my last loop. I havent figured a way on how to check if the division is giving any decimal points in order to stop the loop. This is my code

#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;
}
Was it helpful?

Solution 

#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;
}

OTHER TIPS

#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;
}

#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;
}

The answer is 4. This is clearly correct; it is the GCD of 32 and 60; everything else is divisible by 4.

If desired, you could optimize the loop with:

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

When the GCD is 1, it won't get any bigger,

 #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;
}

  #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;
  }

#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);
 }

#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*\

#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
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top