#include <cstdio>

#define FOR(i, s, d) for(i= (s); i < (d); ++i)

int k, A[32], C[32][32], H[32];
long long n, sol;

int gcd(long long a, int b)
{
  while(a && b)
    if(a >= b)
      a %= b;
    else
      b %= a;
  return a | b;
}

void doit(int i, int nr, long long p)
{
  if(p > n)
    return;
  if(i == k)
  {
    if(nr & 1)
      sol += n / p * H[nr];
    else
      sol -= n / p * H[nr];
    return ;
  }
  doit(i + 1, nr, p);
  doit(i + 1, nr + 1, p / gcd(p, A[i]) * A[i]);
}

int main()
{
  int i, j;
  freopen("light2.in", "r", stdin);
  freopen("light2.out", "w", stdout);
  scanf("%lld", &n);
  scanf("%d", &k);
  FOR(i, 0, k)
    scanf("%d", &A[i]);
  C[0][0] = 1;
  FOR(i, 1, k + 1)
  {
    C[i][0] = C[i][i] = 1;
    FOR(j, 1, i)
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }
  FOR(i, 1, k + 1)
    FOR(j, i % 2, i + 1)
      H[i] += C[i][j], ++j;
  doit(0, 0, 1);
  printf("%lld\n", sol);
  return 0;
}