#include <fstream.h>

#define N 1000000001

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

bool light[N];
long long n,k,nr,max=-1;

void ciur(){
    long long i,j;

	for(i=1;i<=max;++i)

		if(light[i])

			for(j=2;j*i<=n;++j)
					
				light[j*i] = 1-light[j*i];

	for(i=1;i<=n;++i)
		if(light[i])++nr;

}


int main(){
	long long i,di;
		
	fin>>n>>k;
	for (i=1; i<=k; i++){
		fin>>di;
		light[di] = 1-light[di];
		
		if (di > max) max = di;
		
	}
	
	ciur();
	
	fout<<nr;
	
	return 0;
}