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

using namespace std;

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