#include<cstdio>
int n,k,x,n1,nr,da,nda,nx[22],a[1000001];
int main()
{
	freopen("light2.in","r",stdin);
	freopen("light2.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&k);
	int i; int j; nr=0;
	for(i=1;i<=k;i++)
	{
		scanf("%d",&x);
		da=1; nda=0;
		for(j=1;j<=nr;j++)
			if(x==nx[j])
				nda++;
		if(nda%2==1)
			da=0;
		if(da)
		{
			nr++;
			nx[nr]=x;
		}
	}
	for(i=1;i<=nr;i++)
		for(j=nx[i];j<=n;j+=nx[i])
			a[j]=(a[j]+1)%2;
	n1=0;
	for(i=1;i<=n;i++)
		if(a[i]==1)
			n1++;
	printf("%d\n",n1);
	return 0;
}