#include <bits/stdc++.h>

using namespace std;

ifstream f ("light2.in");
ofstream g ("light2.out");

const int Dim = 1e6 + 5;

long long n, ans, v[50];
int k, c[Dim];

long long FindGcd (long long a, long long b) {
    long long r = a % b;
    while (r) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

void bkt (int pos, int lcm, int sgn, int nr) {
    if (lcm > n) return;
    if (pos > k) {
        ans += sgn * n * nr / lcm;
        return;
    }

    bkt (pos + 1, lcm, sgn, nr);
    if (sgn == 1)
        bkt (pos + 1, lcm * v[pos] / FindGcd(lcm, v[pos]), -1, nr + 1);
    else
        bkt (pos + 1, lcm * v[pos] / FindGcd(lcm, v[pos]), 1, nr + 1);
}

int main() {
    f >> n >> k;
    int mx = 0;
    for (int i = 1; i <= k; ++ i) {
        int x; f >> x;
        c[x] = 1 - c[x];

        mx = max (mx, x);
    }

    k = 0;
    for (int i = 1; i <= mx; ++ i)
        if (c[i]) v[++k] = i;

    bkt (1, 1, 0, 0);
    g << ans << '\n';

    return 0;
}