#include <stdio.h>
#include <vector>
#define ll long long
#define NMAX (1<<22)
#define HMAX (1<<21)
#define LMAX 23
using namespace std;
ll n,rez,B[HMAX],rez2;
int k,A[LMAX];
ll cmmdc(ll x,ll y)
{
	ll act;
	while (y)
	{
		act=x%y;
		x=y; y=act;
	}
	return x;
}
int calcul(int x)
{
	if (x==0)
		return 0;
	return 1+calcul(x & (x-1));
}
int main()
{
	freopen("light2.in","r",stdin);
	freopen("light2.out","w",stdout);
	scanf("%lld%d",&n,&k);
	int i,error=0,nr,biti=0,poz,tip,nrb;
	for (i=1; i<=k; i++)
		scanf("%d",&A[i]);
	nr=1<<k;
	B[0]=1;
	ll act;
	for (i=1; i<nr; i++)
	{
		nrb=calcul(i);
		if (i>=(1<<biti))
			biti++;
		poz=i-(1<<(biti-1));
		error=0; act=1; tip=0;
		if (B[poz]>n)
		{
			error=1;
			if (i<(1<<(k-1)))
				B[i]=B[poz];
		}
		else
		{
			if (i<(1<<(k-1)))
			{
				B[i]=B[poz]*A[biti]/cmmdc(B[poz],A[biti]);
				if (B[i]>n)
					error=1;
			}
			else
			{
				tip=1;
				act=B[poz]*A[biti]/cmmdc(B[poz],A[biti]);
				if (act>n)
					error=1;
			}
		}
		if (!error)
		{
			if (!tip)
			{
				if (nrb&1)
					rez+=(n/B[i])*(1<<(nrb-1));
				else
					rez-=(n/B[i])*(1<<(nrb-1));
			}
			else
			{
				if (nrb&1)
					rez+=(n/act)*(1<<(nrb-1));
				else
					rez-=(n/act)*(1<<(nrb-1));
			}
		}
	}
	printf("%lld\n",rez);
	return 0;
}