#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;
}

int d[MAXK], 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++) {
        fscanf(fi,"%d " ,&d[i]);
    }
    bkt(0, 0, 1);
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}