#include <cstdio>
#include <cassert>

using namespace std;

#define LL long long
#define MAXN 1000000000000LL
#define MAXK 22

LL N, Nleft;
int K;
int d[MAXK];

inline LL gcd(LL A, LL B) {
    LL C;
    while (B) {
        C = A % B;
        A = B;
        B = C;
    }
    return A;
}

void back(int lvl, LL prod, int cnt) {
    if (prod > N) {
        return;
    }

    if (lvl == K) {
        if (!cnt) {
            return;
        }

        if (cnt % 2 == 1) {
            Nleft += (N / prod) * (1 << (cnt - 1));
        } else {
            Nleft -= (N / prod) * (1 << (cnt - 1));
        }
        return;
    }

    back(lvl + 1, prod, cnt);
    back(lvl + 1, prod * d[lvl] / gcd(prod, d[lvl]), cnt + 1);
}

int main() {
    assert(freopen("light2.in", "rt", stdin));
#ifndef DEBUG
    assert(freopen("light2.out", "wt", stdout));
#endif

    assert(scanf("%lld", &N) == 1);
    assert(3 <= N && N <= MAXN);
    assert(scanf("%d", &K) == 1);
    assert(1 <= K && K <= MAXK);
    for (int i = 0; i < K; i++) {
        assert(scanf("%d", d + i) == 1);
        assert(1 <= d[i] && d[i] <= 1000000 && d[i] <= N);
    }

    Nleft = 0;
    back(0, 1, 0);
    printf("%lld\n", Nleft);

    /*
    6
        + 2         1
        + 3         1
        - 6         -2
    30
        + 2         1
        + 3         1
        + 5         1
        - 6         -2
        - 10        -2
        - 15        -2
        + 30        4
    210
        + 2         1
        + 3         1
        + 5         1
        + 7         1
        - 6         -2
        - 10        -2
        - 14        -2
        - 15        -2
        - 21        -2
        - 35        -2
        + 30        4
        + 42        4
        + 70        4
        + 105       4
        - 210       -8
    */

    return 0;
}