#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) {
    if(bit == k) {
        if(conf == 0) {
            return ;
        }
        int cnt = __builtin_popcount(conf);
        if(cnt & 1)
            ans += (n / val) * (1 << (cnt - 1));
        else
            ans -= (n / val) * (1 << (cnt - 1));
    }
    else {
        bkt(bit + 1, conf, val);
        val /= gcd(d[bit], val);
        if(INF / val >= d[bit])
            bkt(bit + 1, conf ^ (1 << bit), val * d[bit]);
    }
}

int main() {
    FILE *fi, *fout;
    int i;
    fi = fopen("light2.in" ,"r");
    fout = fopen("light2.out" ,"w");
    fscanf(fi,"%lld %d " ,&n,&k);
    for(i = 0; i < k; i++) {
        int x;
        fscanf(fi,"%d " ,&x);
        d.push_back(x);
    }
    sort(d.begin(), d.end());
    d.resize(unique(d.begin(), d.end()) - d.begin());
    k = d.size();
    bkt(0, 0, 1);
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}