
//================code===================//

//#define TLE

#ifdef TLE
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <ctime>


#define ci(t) cin>>t
#define co(t) cout<<t
#define LL long long

#define ld double
#define fa(i,a,b) for(LL i=(a);i<(LL)(b);++i)
#define fd(i,a,b) for(LL i=(a);i>(LL)(b);--i)
#define setp tuple<LL,LL,LL>
#define setl pair<LL,LL>
#define micro 0.000001

using namespace std;

LL gcd(LL a, LL b) { return a % b ? gcd(b, a % b) : b; }


#ifdef OHSOLUTION
#define ce(t) cerr<<t
#define AT cerr << "\n=================ANS=================\n"
#define AE cerr << "\n=====================================\n"
#define DB(a) cerr << __LINE__ << ": " << #a << " = " << (a) << endl;
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#else
#define AT
#define AE
#define ce(t)
#endif

pair <int, int> vu[9] = { {0,-1},{1,0},{0,1} ,{-1,0},{0,0},{1,1}, {-1,1} , {1,-1},{-1,-1} }; //RDLU EWSN

template<typename T, typename U> void ckmax(T& a, U b) { a = a < b ? b : a; }
template<typename T, typename U> void ckmin(T& a, U b) { a = a > b ? b : a; }
struct gcmp { bool operator()(LL a, LL b) { return a < b; } bool operator()(setl& a, setl& b) { return a.second < b.second; } };
struct lcmp { bool operator()(LL a, LL b) { return a > b; } bool operator()(setl& a, setl& b) { return a.second > b.second; } };

const int max_v = 1e5+ 7;
const int max_k = 1e1 + 7;
const int INF = 1e9 + 7;
const LL LNF = (LL)5e18 + 7ll;
LL mod = 998244353;
template<typename T, typename U> void MOD(T& a, U b) { a += b; if (a >= mod) a -= mod; }


int main()
{
#ifdef OHSOLUTION
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; ci(n);
	
	vector<int> vi(n);
	fa(i, 0, n) ci(vi[i]);

	vector<int> prime;
	vector<int> sp(57);

	fa(i, 2, 57)
	{
		if (!sp[i]) prime.push_back(i);
		for (auto& x : prime)
		{
			if (i * x >= 57) break;
			sp[i * x] = x;
			if (i % x == 0) break;
		}
	}

	vector<int> tar;
	LL ans = LNF;

	auto check = [&](LL x)
	{
		fa(i, 0, n)
		{
			if (gcd(x, vi[i]) == 1) return false;
		}
		return true;
	};

	fa(i, 0, 1 << 15)
	{
		tar.clear();
		LL tmp = 1;

		fa(j, 0, 15) if (i & (1 << j)) tar.push_back(prime[j]),tmp*=prime[j];

		if(check(tmp)) ckmin(ans,tmp);
	}

	co(ans);

	return 0;
}

#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;

#define REP(i,b,e) for(int i=b; i<e; i++)
#define PRINT(vec) {printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");}
#define fi first
#define se second

const int MOD = 1e9+7;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	ll n;
	scanf("%ld", &n);

	std::set<ll> st;
	REP(i, 2, 100000){
		ll x = i;
		REP(j, 2, 40){
			x *= i;
			if(x>n) break;
			st.insert(x);
		}
	}
	printf("%ld\n", n - st.size());		
	return 0;
}

