#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define sh short int
#define LL long long
#define pb push_back
int v[25],a[25];
LL N,ap;
sh K,nr;
inline void unic()
{
	int x=v[1];
	int num=1;
	for (int i=2; i<=nr; ++i)
	{
		if (v[i]==v[i-1])
			++num;
		else
		{
			if (num&1)
				a[++a[0]]=x;
			x=v[i];
			num=1;
		}
	}
	if (num&1)
		a[++a[0]]=x;
}
inline void citire()
{
	freopen("light2.in","r",stdin);
	freopen("light2.out","w",stdout);
	scanf("%lld%hd",&N,&K);
	for (sh i=1; i<=K; ++i)
	{
		scanf("%d",&v[++nr]);
		if (v[i]>N)
			--nr;
	}
	sort(v+1,v+1+nr);
	unic();
}
inline void light()
{
	sh num;
	bool ok;
	if (a[1]==1)
	{
	for (LL i=a[2]; i<=N; )
	{
		ok=true;
		num=0;
		for (sh j=2; j<=a[0]; ++j)
		{
			if (i<a[j])
			{
				i=a[j];
				ok=false;
				break;
			}
			if (i%a[j]==0)
				++num;
		}
		i+=ok;
		ap+=(num&1);
	}
		printf("%lld",N-ap);
		return;
	}
	for (LL i=a[1]; i<=N; )
	{
		ok=true;
		num=0;
		for (sh j=1; j<=a[0]; ++j)
		{
			if (i<a[j])
			{
				i=a[j];
				ok=false;
				break;
			}
			if (i%a[j]==0)
				++num;
		}
		i+=ok;
		ap+=(num&1);
	}
		printf("%lld",ap);
}
int main()
{
	citire();
	light();
	return 0;
}