#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int n, a[100007], mx, ps[78498 + 10], lp[1000007], top = 0;
int f[1000007];
int trans[1000007];
ll p[1000007];

int main()
{
    freopen ("pairs.in", "r", stdin);
    freopen ("pairs.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] > mx)
        {
            mx = a[i];
        }
    }


    for (int i = 2; i <= mx; i++)
    {
        if (lp[i] == 0)
        {
            lp[i] = i;
            ps[++top] = i;
        }
        for (int j = 1; j <= top && ps[j] <= lp[i] && ps[j] * i <= mx; j++)
        {
            lp[ps[j] * i] = ps[j];
        }
    }

    cout << top << "\n";
    return 0;


    trans[1] = 1;

    for (int i = 2; i <= mx; i++)
    {
        if (lp[i / lp[i]] == lp[i])
        {
            trans[i] = trans[i / lp[i]];
        }
        else
        {
            trans[i] = trans[i / lp[i]] * lp[i];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        f[a[i]]++;
    }

    for (int i = 1; i <= mx; i++)
    {
        if (trans[i] == i)
        {
            for (int j = 2 * i; j <= mx; j += i)
            {
                f[i] += f[j];
            }
        }
    }

    for (int i = mx; i >= 1; i--)
    {
        if (trans[i] == i)
        {
            p[i] = f[i] * (ll) (f[i] + 1) / 2;
            for (int j = 2 * i; j <= mx; j += i)
            {
                p[i] -= p[j];
            }
        }
    }

    printf("%lld\n", p[1]);
    return 0;
}