#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXK = 21;

inline ll gcd(ll a, ll b) {
    ll r;
    while(b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

vector <int> d;
int k;
ll ans, n;

void bkt(int bit, int conf, ll val, int cnt) {
    if(val > n) {
        return ;
    }
    if(bit == k) {
        if(conf == 0) {
            return ;
        }
        if(cnt & 1)
            ans += (n / val) * (1 << (cnt - 1));
        else
            ans -= (n / val) * (1 << (cnt - 1));
    }
    else {
        bkt(bit + 1, conf, val, cnt);
        val /= gcd(d[bit], val);
        bkt(bit + 1, conf ^ (1 << bit), val * d[bit], cnt + 1);
    }
}

int main() {
    FILE *fi, *fout;
    int i;
    fi = fopen("light2.in" ,"r");
    fout = fopen("light2.out" ,"w");
    fscanf(fi,"%lld %d " ,&n,&k);
    map <int, int> mp;
    for(i = 0; i < k; i++) {
        int x;
        fscanf(fi,"%d " ,&x);
        mp[x]++;
    }
    for(auto it : mp) {
        if(it.second & 1)
            d.push_back(it.first);
    }
    k = d.size();
    bkt(0, 0, 1, 0);
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}