#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;
LL n, k;
LL PP[1<<20];
char lst[1<<22];
vector<LL> v;
int main()
{
  freopen("light2.in", "r", stdin);
  freopen("light2.out", "w", stdout);
  cin >> n >> k;
  LL total = 0;
  for (int i = 0; i < k; ++i)
  {
    LL x; cin >> x;
    v.push_back(x);
  }
  k = v.size();
  lst[1] = 0;
  for (int i = 2; i < (1 << k); ++i)
    for (int b = 0; b < k; ++b) if (i & (1 << b))
      lst[i] = b;
  PP[0] = 1;
  for (int mask = 1; mask < (1 << k); ++mask)
  {
    LL p = __builtin_popcount(mask);
    LL P = 1;
    int mare = 0;
    int prev = mask ^ (1 << lst[mask]); 
    if (prev < (1 << 20)) 
    {
      P = PP[prev];
      LL g = __gcd(P, v[lst[mask]]);
      P = P * v[lst[mask]]; P /= g;
      if (P > n) P = n + 1, mare = 1;
      if (mask < (1 << 20))
      PP[mask] = P; 
    } else
    {
      P = 1;
      int prev = mask;
      for (int i = k - 1; i >= 0; --i) if (prev & (1 << i))
      {
        LL g = __gcd(P, v[i]);
        P = (P * v[i]) / g;
        if (P > n) {P = n + 1, mare = 1; break;}
        prev ^= (1 << i);
        if (prev < (1 << 20)) break;
      }
      LL g = __gcd(P, PP[prev]);
      P = P * PP[prev]; P /= g;
      if (P > n) mare = 1;
    }
    if (mare) continue;
    if (p % 2 == 1)
    {
      --p;
      total += (1LL<<p) * (n / P);
    }
    else
    {
      --p;
      total -= (1LL<<p) * (n / P);
    }
  }
  cout << total << '\n';
  return 0;
}