Find the maximum GCD of a number with respect to all the values in an array for competitive programming

Question

Here is the Question. Find the largest GCD of the input variable with the values of an array.

Inputs are as follows:- First-line contains two integers, N and Q.

Second-line contains N integers which form the arr[].

Next, Q lines contain an integer M, the time in seconds she wishes to go back.

#include <stdio.h>

int main(){
    int n,q;
    scanf("%d %d", &n,&q);
    int a[n];
    int gcdn[n];
    for (int i = 0;i < n; i++) {
        scanf("%d",&a[i]);      }
    while (q>0){
        q--;
        int x;
        int max = 0;
        scanf("%d",&x);
        max = gcd(a[0],x);
        for(int i=0;i<n;i++) {
            int t = gcd(a[i],x);
            if(t > max)
                max = t;
        }
        printf("%d \n",max);
    }

}

int gcd (int a, int b) {
    if (b==0)
        return a;
    else 
        return gcd(b, a%b);
}

How can I make this code better in terms of competitive programming? And what other languages can make this code better and more efficient?

Answer 1

1. gcdn[] is unused.

2. if n==0, you access a non-existent array element, and even if it isn't, you do the GCD with a[0] twice.

3. gcd() is called before it is declared, which is bad style and can mess up optimization.

4. you might think about whether the M or arr[] elements are likely to be larger. The order you pass values to gcd() can reduce by one loop if you guess right.

5. The tail recursion on gcd() should be OK as long as you optimize.