#include <fstream.h>

#define N 10000001

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

char light[N];
long long n,k,nr,max=-1,el[23];

void ciur(){
    long long i,j;

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

		if(light[i]){
			
			light[i] = 1;

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

}


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