#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,rc,rez;
int nr1,k,vi[25],v[25];
void read()
{
  freopen("light2.in","r",stdin);
  freopen("light2.out","w",stdout);
  scanf("%lld",&n);
  scanf("%d",&k);
  for(int i=1;i<=k;i++)
    scanf("%d",&vi[i]);
}
void norm()
{
  int newk=0,nrap=1;
  sort(vi+1,vi+k+1);
  for(int i=2;i<=k;i++)
    if(vi[i]!=vi[i-1])
    {
      if(nrap%2)
        v[++newk]=vi[i-1];
      nrap=1;
    }
    else
      nrap++;
  if(nrap%2)
    v[++newk]=vi[k];
  k=newk;
}
ll cmmdc(ll x,ll y)
{
  if(x==0)
    return y;
  if(y==0)
    return x;
  ll r=x%y;
  while(r)
  {
    x=y;
    y=r;
    r=x%y;
  }
  return y;
}
void back(int poz)
{
  if(rc>n)
    return;
  if(poz>k)
  {
    if(nr1%2==1)
      rez+=(ll)(1<<(nr1-1))*(n/rc);
    else if(nr1)
      rez-=(ll)(1<<(nr1-1))*(n/rc);
    return;
  }
  back(poz+1);
  ll aux=cmmdc(rc,v[poz]);
  nr1++;
  rc=rc/aux*(ll)v[poz];
  back(poz+1);
  nr1--;
  rc=rc/(ll)v[poz]*aux;
}
int main()
{
  read();
  norm();
  for(int i=1;i<=k;i++)
  {
    rc=v[i];
    nr1=1;
    back(i+1);
  }
  printf("%lld",rez);
  return 0;
}