#include <fstream.h>

#define N 1000000001

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

char 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)
				if (light[j*i] == 2)
					light[j*i] = 3;
				else
					if (light[j*i] != 3)
						light[j*i] = 1-light[j*i];
					else 
						light[j*i] = 1;
				
		}

}


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