#include <fstream>
#define nmax 99999999

using namespace std;

ifstream fin("light2.in");
ofstream fout("light2.out");

int n, k, nr;
int d[nmax], stare[nmax], uz[nmax];

int main()
{
    int i, j;
    fin >> n >> k;
    if(n > nmax) return 0;
    for(i=1; i<=k; ++i)
    {
        fin >> d[i];
        ++uz[d[i]];
    }
    // sort(d+1, d+k+1);
    for(i=1; i<=k; ++i)
    {
        if(uz[d[i]]%2)
            for(j=1; j*d[i]<=n; ++j)
                if(stare[j*d[i]]) stare[j*d[i]]=0, --nr;
                else stare[j*d[i]]=1, ++nr;
    }
    fout << nr << "\n";
    return 0;
}