C Programming Language

Problem is to create a program that will find the greatest GCD in an array of numbers. I can get the correct answers but my problem is efficiency and the checking software marks my answer wrong with the reason: TIMELIMIT. Code attempted is given below.

#include

int gcd(int n1, int n2) { int i, gcd; for(i=1; i

int findGGCD(int arr[], int n) { int i, j; int ggcd = 0; for (i = 0; i arr[j+1] && arr[j+1]!=0) { k = gcd(arr[j+1], arr[i] % arr[j+1]); } else if(arr[i] > arr[j+1] && arr[j+1]==0) { k = arr[i]; } else { k = gcd(arr[i], arr[j+1]); } if(k > ggcd) { ggcd = k; } } } return ggcd; }

int main() { int cases; scanf("%d", &cases); if(cases100) { return 1; } for(int q = 1; q100) { return 1; } int ggcd; int arr[n]; for(int i = 0; i1000000000) { return 1; } } ggcd = findGGCD(arr, n); printf("Case #%d: %lld ", q, ggcd); } }<>

Euclidean algorithm is an efficient method for computing greatest common divisor (GCD) of 2 numbers, the argest positive integer that divides both of then without leaving a remainder. For example, the GCD of 8 and 12 is 4. To caloulate the GCD, we could use the equation below GCD(a,b) GCD(b,a%b) GCD(a,b)-a ifa>band b !:0 if a > b and b-0 This problem is very simple, you just have to read N number and print the greatest of GCD (GGCD). To find GGCD, you must find the GCD of all pairs (a, a) where i-j and find the largest GCD Format Input The input starts with an integer T represents the number of test cases. Each test case will start with an integer N, the number of numbers to read. The next line will contain N integers a as the numbers to be read. Format Output For each test case, prnt Case #X: Y. where X s the test number and Y ls the GGCD. T100 2N100 lcza,c= 1 000 000 000 Sample Input (standart input) Sample Output (standard output) Case 1: 25 Case 2: 11 10 25 15 30 50 117 33 5 S 7 Al pars. GCD in Case #2: GCD 10, 11)1 GCD 10, 34) 2 GCD 10, 22) 2 GCD 11, 34)1 GCD(11, 22) 11 GCD(34, 22) 2 Therefore, GGCD 11