char a[200004];
int main(){
	long n,m;
	scanf("%ld%ld",&n,&m);
	for(long i=0;i<m;++i){
		long x;
		scanf("%ld",&x);
		a[x]^=1;
	}
	for(long i=n;i;--i){
		if(a[i]){
			--n;
			long j;
			for(j=1;j*j<i;++j){
				if(i%j==0){
					a[j]^=1;
					a[i/j]^=1;
				}
			}
			if(j*j==i){
				a[j]^=1;
			}
		}
	}
	printf("%ld",n);
}