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

using namespace std;

typedef long long LL;
LL n, k;
LL PP[1<<21];
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]); 
    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 << 21))
    PP[mask] = P; 
    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;
}