/*
       This sky
       Is lonely and grey
       But every night I feel your gravity waves
       And the world is cold
       But it's beautiful
       I wish you were here now
       I miss your soul
       But you lost your light
       When the darkness called
       I still stand here waiting
       The last to fall
       The last to fall
       The last to fall
       The last to fall
                            */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const unordered_map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC targett("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define dbg(x) cout<<#x<<" = "<<x<<'\n';
#define fri(i,s,n) for(ll i=s;i<n;i++)
#define mod 1000000007
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define inf 4e18
#define five 100005;
#define six 1000005;
#define printclock cerr<<"Time"<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//_______________________________________________________________________________________
const int N = six;
vector<int> fct[N];
int frq[N];
int main()
{
       for(int i = 2 ; i < N ; i++)
       {
              for(int j = i ; j < N ; j += i)
              {
                     fct[j].pb(i);
              }
       }
       int one = 0;
       memset(frq,0,sizeof frq);
       int n;
       cin>>n;
       int a[n];
       arrin(a,n);
       fri(i,0,n){
              frq[a[i]]++;
              if(a[i]==1){
                     one++;
                     continue;
              }
       }
       if(one==1){
              cout<<1<<endl;
              return 0;
       }
       if(one>1){
              cout<<0<<endl;
              return 0;
       }
       int ans = 0;
       fri(i,0,n){
              bool ff = true;
              for(int j : fct[a[i]]){
                     if(j==a[i]){
                     if(frq[j]>1){
                            ff=false;
                     }}
                     else{
                            if(frq[j]){
                                   ff = false;
                            }
                     }
              }
              ans += ff;
       }
       cout<<ans<<endl;

}


Measured memory_bytes: 118736