#include<bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp> 
    #include <ext/pb_ds/tree_policy.hpp> 
    using namespace __gnu_pbds;
    using namespace std;
     
    #define ff                  first
    #define ss                  second
    #define endl                "\n"
    #define loop(i,s,e)         for(int i=s;i<e;i++)
    #define int                 long long
    #define vi                  vector<int> 
    #define S(v)                sort(v.begin(),v.end())
    #define RS(v)               sort(v.rbegin(),v.rend())
    #define R(v)                reverse(v.begin(),v.end())
    #define mxpq(T)             priority_queue <T>
    #define mnpq(T)             priority_queue<T,vector<T>,greater<T>>
    #define prv(v)              for(auto &x : v)cout << x << " ";
    #define piirv(v)            for(auto &x : v)cout << x.ff << " " << x.ss << endl;
    #define prvv(v)             for(auto &x : v)for(auto &y : x.ss)cout << y << " ";
    #define mp                  make_pair
    #define pii                 pair<int,int>
    #define mset(a,f)           memset(a , f , sizeof(a))
    #define pb                  push_back
    #define inf                 INT_MAX
    #define INF                 LLONG_MAX
    typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
     
    const int N = 1e6 + 6;
    const int M = 1e9+7;
    int A[N];
    int lp[N];
    int n , m;
    vector<int> prime;

    void linear_sieve()
    {
        mset(lp,0);
        prime.clear();
        loop(i,2,N)
        {
            if(lp[i] == 0)
            {
                prime.pb(i);
                lp[i] = i;
            }
            
            for(int j = 0; j < (int)prime.size() && i*prime[j] < N; j++)
            {
                lp[i*prime[j]] = prime[j];
            }
        }
    }
     

    void solve()
    {
        int n;
        cin >> n;

        map<int,int> mm;
        map<int,int> id;

        linear_sieve();

        loop(i,0,n)
        {
            cin >> A[i];
            mm[A[i]]++;
        }

        map<int,int> frq;

        vector<int> ans;

        int cnt = 0;

        if(mm.find(1)!=mm.end())
        {
            if(mm[1] == 1)cout << 1 << endl;
            else cout << 0 << endl;
            return;
        }

        for(auto &it :  mm)
        {
            if(it.ss > 1)
            {
                frq[it.ff]++;
                continue;
            }
            if(lp[it.ff] == it.ff)
            {
                cnt++;
                frq[it.ff]++;
                continue;
            }
            int ok = 0;
            for(int i = 1; i*i <= it.ff; i++)
            {
                if(it.ff%i == 0 && (frq.find(i)!=frq.end() || frq.find(it.ff/i)!= frq.end()))
                {
                    ok = 1;
                    break;
                }
            }
            frq[it.ff]++;
            if(!ok)
            {
                cnt++;
                // cout << it.ff << " " << it.ss << endl;
            }
        }

        cout << cnt;
    }           
     
    int32_t main()
    {
     
    cout<<fixed<<setprecision(16);
     
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
        
     
        int t = 1;
        // cin >> t;
        while(t--)solve();
      
    }


Measured memory_bytes: 38112