#include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(i=a;i<b;i++)
    #define pb push_back
    #define all(v) v.begin(),v.end()
    #define F first
    #define S second
    #define vi vector < ll  int >
    #define CLR(a) memset((a),0,sizeof(a))
    #define mp make_pair
    #define hell 1000000007
    using namespace std;

    #define MAXN 1000005
    int spf[MAXN];
    void sieve()
    {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)
            spf[i] = i;
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;

        for (int i=3; i*i<MAXN; i++)
        {
            if (spf[i] == i)
            {
                for (int j=i*i; j<MAXN; j+=i)

                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }


    vector<int> gf(int x)
    {
        vector<int> ret;
        while (x != 1)
        {
            ret.push_back(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }
    int BIT[100050]; //fenwick
    void upd(int x) { ++x;  while(x<=MAXN)  {  BIT[x]++;  x+=(x&-x);  } }
    int cal(int x) {  ++x;  int res=0;  while(x>0)  {  res+=BIT[x];  x-=(x&-x);  } return res; }
    ll Com[1051][1051];
    void pre()
    {

        ll i,j,n=1051;
        rep(i,0,n) Com[i][0]=Com[i][i]=1;
        rep(i,2,n)
        {
            rep(j,1,i)
            {
                Com[i][j]=Com[i-1][j]+Com[i-1][j-1];
                Com[i][j]%=hell;
            }
        }

    }
    ll mod=hell;
    ll pr( ll x , ll y)
    {
        ll ans=1;
        if(y==0) return ans;
        while(y>1)
        {
            if(y&1) ans*=x;
            x*=x;
            y/=2;
            x%=mod;
            ans%=mod;
        }
        ans*=x;
        ans%=mod;
        return ans;
    }
    ll inv(ll n)
    {
        return pr(n,mod-2);
    }
    ll stoi(string s)
    {
        int n=s.size();
        ll k=0; int i;
        rep(i,0,n)
        {
            k+=s[i]-'0';
            k*=10;
        }
        return k/10;
    }
    string to_string(ll n)
    {  if(!n) return "0";
        string s=""; int a,b;
        while(n>0)
        {
            b=n%10;
            s+=(b+'0');
            n/=10;
        }
        reverse(all(s));
        return s;
    }

    int nlevel[1005]; int prr[1005];
    bool vis[1005];
    void dfs(int node , int par, vector < int > g[])
    {
        nlevel[node]=1+nlevel[par];
        prr[node]=par;
        vis[node]= true;
        for(auto it : g[node])
        {
            if(!vis[it]) dfs(it,node,g);
        }
    }
    void solve()
    {
    int i,j=0,r=200,p,q,k=0,d,y=0,n,h=10000000,flag=0,m=0,a=hell,b=hell,id,h1,h2,a1,b1,a2,w,x,u,f,l,c=0,e;
    cin>>n;
    vector < int > v(n);
    set < int > st;

    vector < int > ans(1000100,-1),ck(1000201,0),cnt(1000100,0);
    rep(i,0,n){
    cin>>v[i]; ck[v[i]]=1; cnt[v[i]]++; }
    if(ck[1])
    {
        if(cnt[1]>1) cout<<0;
        else cout<<cnt[1];
        return;
    }
    for(i=0;i<n;i++)
    {
        if(cnt[v[i]]>1) continue;
        k=v[i];
        if(ans[v[i]]!=-1) {y+=ans[v[i]]; continue;}
        if(spf[k]==k)
        {
            y++;
            ans[k]=1;
            //cout<<k<<" ";
        }
        else
        {   bool okk=1;
            for(j=2;j*j<=k;j++)
            {
                if(k%j==0)
                {
                    if(ck[j] or ck[k/j]) {okk=0; break;}
                }

            }
            if(okk) {y++; ans[k]=1;}
            else ans[k]=0;

        }
    }
cout<<y;
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t=1;
        sieve();
        //cin>>t;
        while(t--)
        solve();
    }


Measured memory_bytes: 19568