まず、\(A_i\) の上限である \(1000\) より大きい数は GCD 度が \(0\) です。ところが \(2 \le A_i\) より \(A_1\) の GCD 度は少なくとも \(1\) なので \(1000\) より大きい数は考慮に入れる必要がないことが分かります。
すると、 \(2\) 以上 \(1000\) 以下のそれぞれの整数 \(k\) について GCD 度を計算してその中で GCD 度が最大だったときの \(k\) を出力すればよいことになります。
「 \(2\) 以上 \(1000\) 以下のそれぞれの整数 \(k\) について 」の処理や、ある整数の GCD 度の計算は繰り返し文を使うと実現できます。GCD 度が最大になるような \(k\) を求めるのは、今までの GCD 度の最大値と、そのときの \(k\) を持つ \(2\) つの変数を用意して、今の GCD 度が今までの GCD 度より大きかったらこの \(2\) つの変数を更新することでできます。

解答例 (C) ※C99 を仮定しています

#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	int a[n];
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	int max = 0;
	int res = -1;
	for (int i = 2; i <= 1000; i++) {
		int cnt = 0;
		for (int j = 0; j < n; j++) if (a[j] % i == 0) cnt++;
		if (max < cnt) max = cnt, res = i;
	}
	printf("%d\n", res);
	return 0;
}

解答例 (Python)

N = int(input())
A = list(map(int, input().split()))
 
ans = -1
mx = 0
 
for x in range(2, 1001):
	s = sum(a % x == 0 for a in A)
	if mx < s:
		mx = s
		ans = x
 
print(ans)