First, for ever integer more than \(1000\), which is the upper bound of \(A_i\), its GCD-ness is \(0\). On the other hand, since \(2 \le A_i\), the GCD-ness of \(A_1\) is at least \(1\), so we do not have to take into account the integers exceeding \(1000\). Now, we want to calculate the GCD-ness for each integer between \(2\) and \(1000\), inclusive, and then output \(k\) that had the maximum GCD-ness. The process of “for each integer \(k\) between \(2\) and \(1000\)” and calculation of GCD-ness of an integer can be achieved by for-loop. In order to find \(k\) that has the maximum GCD-ness, we can prepare two variables, each of which stores the maximum GCD-ness and \(k\) that produces the maximum GCD-ness, and update those two variables if the current GCD-ness is larger than the GCD-ness so far.

Sample Code (C) ＊ C99 is assumed

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

Sample Code (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)