#include <iostream>
#include <algorithm>
//#define space "1627D"
using namespace std;
const int mn=1e6;
int d[mn+5],n,ans=0;
inline void faster()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void sol()
{
cin >>n;
for (int i=1;i<=n;++i)
{
int x;
cin >>x;
d[x]=1;
}
for (int i=mn;i>=1;--i)
{
if (d[i]) continue;
int gcd=-1;
for (int j=2*i;j<=mn;j+=i)
{
if (d[j])
{
if (gcd==-1) {
gcd = j/i;
} else {
gcd = __gcd(gcd,j/i);
}
}
}
if (gcd==1)
{
ans+=1;
d[i]=1;
}
}
cout <<ans<< endl;
}
int main()
{
faster();
#ifdef space
freopen(space".inp", "r", stdin);
freopen(space".out", "w", stdout);
#endif // space
sol();
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgovLyNkZWZpbmUgc3BhY2UgIjE2MjdEIgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IG1uPTFlNjsKaW50IGRbbW4rNV0sbixhbnM9MDsKaW5saW5lIHZvaWQgZmFzdGVyKCkKewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKfQp2b2lkIHNvbCgpCnsKICAgIGNpbiA+Pm47CiAgICBmb3IgKGludCBpPTE7aTw9bjsrK2kpCiAgICB7CiAgICAgICAgaW50IHg7CiAgICAgICAgY2luID4+eDsKICAgICAgICBkW3hdPTE7CiAgICB9CiAgICBmb3IgKGludCBpPW1uO2k+PTE7LS1pKQogICAgewogICAgICAgIGlmIChkW2ldKSBjb250aW51ZTsKICAgICAgICBpbnQgZ2NkPS0xOwogICAgICAgIGZvciAoaW50IGo9MippO2o8PW1uO2orPWkpCiAgICAgICAgewogICAgICAgICAgICBpZiAoZFtqXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKGdjZD09LTEpIHsKCiAgICAgICAgICAgICAgICAgICAgZ2NkID0gai9pOwogICAgICAgICAgICAgICAgfSBlbHNlIHsKCiAgICAgICAgICAgICAgICAgICAgZ2NkID0gX19nY2QoZ2NkLGovaSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYgKGdjZD09MSkKICAgICAgICB7CiAgICAgICAgICAgIGFucys9MTsKICAgICAgICAgICAgZFtpXT0xOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQgPDxhbnM8PCBlbmRsOwp9CmludCBtYWluKCkKewogICAgZmFzdGVyKCk7CiAgICAjaWZkZWYgc3BhY2UKICAgICAgICBmcmVvcGVuKHNwYWNlIi5pbnAiLCAiciIsIHN0ZGluKTsKICAgICAgICBmcmVvcGVuKHNwYWNlIi5vdXQiLCAidyIsIHN0ZG91dCk7CiAgICAjZW5kaWYgLy8gc3BhY2UKICAgIHNvbCgpOwogICAgcmV0dXJuIDA7Cn0K