//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define S 1000001
#define M 1000000007
#define nl cout<<"\n";
#define er  cout<<"\n***********\n";
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test lli t;  cin>>t; while(t--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define Y cout<<"Yes\n";
#define N cout<<"No\n";
#define print(x)                 cout<<#x<<": "<<x<<endl;
#define print2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl;
#define print3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define print4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define print5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl;
#define print6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl;
lli arr[1000001];
lli mpp[1000001],mpp2[1000001];
void seive()
{
    arr[1]=arr[0]=1;
    for(lli i=2;(i*i)<=1000000;i++)
    {
        if(arr[i]==0)
        {
            for(lli j=i*i;j<=1000000;j=j+i)
            {
                arr[j]=1;
            }
        }
    }
}
int main()
{
    fast
    lli n,ans=0;
    seive();
    cin>>n;
    vector<lli> v(n);
    for(lli i=0;i<n;i++)
    {
        cin>>v[i];
        mpp[v[i]]++;
    }
        
    for(lli i=0;i<n;i++)
    {
        lli ele=v[i];
        if(arr[ele]==0)
        {
            if(mpp[1]>=1||mpp[ele]>=2)
            {
                
                ;
            }
            else
            {
                ans++;
            }
            continue;
        }
        if(mpp2[ele]==INT_MAX||mpp2[ele]==INT_MIN)
        {
            if(mpp2[ele]==INT_MAX)
            {
                ans++;
            }
            continue;
        }
        bool f=0;
        for(lli j=1;(j*j)<=ele;j++)
        {
            // er
            if(j==1)
            {
                if(ele==1)
                {
                    if(mpp[1]>=2)
                    {
                        f=1;
                        break;
                    }
                    
                }
                else
                {
                   if(mpp[1]>=1||mpp[ele]>=2) 
                   {
                       f=1;
                       break;
                   }
                }
               
               continue; 
            }
            if((ele%j)==0)
            {
                if(mpp[j])
                {
                    f=1;
                    break;
                }
                if(j*j!=ele)
                {
                    if(mpp[ele/j])
                    {
                        f=1;
                        break;
                    }
                }
                // print2(j,ele/j)
            }
        }
        if(f==0)
        {
            ans++;
            mpp2[ele]=INT_MAX;
        
        }
        else
        {
        mpp2[ele]=INT_MIN;
        }
    }
    
    cout<<ans;
}
//a+b=a⊕b+2∗(a&b)
//__builtin_popcount(number)
//cout<<fixed<<setprecision(8)<<output<<"\n";




Measured memory_bytes: 28140