#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for(ll i=0; i<(n); ++i) #define TEN(x) ((ll)1e##x) #define ALL(v) (v).begin(), (v).end() // エラトステネスのふるい O(n log log n) : t[i] = true ⇔ iが素数 (i <= n) vector sieve_of_eratosthenes(ll n) { vector t(n+1, true); t[0] = t[1] = false; for(ll i = 2; i <= n; ++i) if (t[i]){ for(ll j = 2*i; j <= n; j += i) t[j] = false; } return t; } vector get_occur_list(ll x) { vector occur(10, 0); while (x!=0) { occur[x % 10]++; x /= 10; } return occur; } int main(){ vector a(10, false); ll n; cin >> n; REP(_, n) { ll i; cin >> i; a[i] = true; } vector p; p.reserve(5000000); { auto t = sieve_of_eratosthenes(5000000); REP(i, t.size()) if (t[i]) p.push_back(i); } ll max_interval = -1; vector occur(10, 0); ll end = -1; REP(i, p.size()) { auto _ = get_occur_list(p[i]); REP(j, 10) occur[j] += _[j]; REP(j, 10) if(!a[j]) while(occur[j]!=0){ end++; auto _ = get_occur_list(p[end]); REP(k, 10) occur[k] -= _[k]; } bool valid = true; REP(j, 10) if (a[j]) if (occur[j] == 0) valid = false; if (valid) { ll k = (end == -1) ? 1 : p[end] + 1 ; ll l = (i == p.size() - 1) ? 5000000 : p[i+1] - 1 ; max_interval = max(max_interval, l - k); } } cout << max_interval << endl; return 0; }