#include <bits/stdc++.h>
using namespace std;

long long gcd(long long x, long long y) {
    if (y == 0)
        return x;
    else
        return gcd(y, x%y);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, K;
    cin >> N >> K;
    vector<long long> a;
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        if (x > 1)
            a.push_back(x);
    }

    constexpr int MAX = 1'000'000;
    if (N <= MAX) {
        bitset<MAX + 1> bs;
        for (int i = 1; i <= N; i++)
            bs[i] = true;
        for (auto x : a) {
            for (int idx = 1; idx <= N; idx += x)
                bs[idx] = false;
        }
        cout << bs.count() << '\n';
    } else {
        long long pigs = N;
        K = a.size();
        for (int mask = 1; mask < (1 << K); mask++) {
            long long lcm = 1;
            int bits = 0;
            for (int i = 0; i < K; i++) {
                if (mask & (1 << i)) {
                    long long g = gcd(lcm, a[i]);
                    long long new_factor = a[i] / g;
                    if (lcm > N / new_factor) {
                        lcm = N + 1; // essentially to big to have any impact
                    } else {
                        lcm *= new_factor;
                    }
                    bits++;
                }
            }
            if (bits % 2)
                pigs -= (N + (lcm - 1)) / lcm;
            else
                pigs += (N + (lcm - 1)) / lcm;
        }
        cout << pigs << '\n';
    }
}