Cerința

Se dă un şir format din n numere naturale nenule. Aflaţi cel mai mic număr natural, diferit de 1, care divide un număr maxim de numere din şir.

Date de intrare

Fișierul de intrare divizor112.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire

Fișierul de ieșire divizor112.out va conține pe prima linie cel mai mic număr natural, diferit de 1, care divide un număr maxim de numere din şir.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

divizor112.in

5
1 2 3 4 5

divizor112.out

2

Explicație

2 divide două numere din şir.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("divizor112.in");
ofstream cout("divizor112.out");
int n , f[1000001] , maxi , rez , x;
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        for(int j = 1 ; j * j <= x; j ++)
        {
            if(x % j == 0)
            {
                f[j]++;
                if(j*j != x) f[x/j]++;
            }
        }
    }
    for(int i = 2 ; i <= 1000000 ; i++)
    {
        if(f[i] > maxi)
        {
            maxi = f[i];
            rez = i;
        }
    }
    cout << rez;
}