#include <fstream>
using namespace std;

ifstream cin ("light2.in");
ofstream cout ("light2.out");

int64_t Cmmdc (const int64_t valoare_1 , const int64_t valoare_2)
{
    return valoare_2 ? Cmmdc(valoare_2 , valoare_1 % valoare_2) : valoare_1;
}

int lungime , sir[32];
int64_t limita , total;

void Backtracking (const int indice , const int setati , const int64_t actual)
{
    if (actual > limita)
        { return; }

    if (indice > lungime) {
        if (setati) {
            if (!(setati & 1)) { total -= limita / actual * (1 << (setati - 1)); }
            else { total += limita / actual * (1 << (setati - 1)); }
        }
        return;
    }

    Backtracking(indice + 1 , setati , actual);
    Backtracking(indice + 1 , setati + 1 , actual / Cmmdc(actual , sir[indice]) * sir[indice]);
}

int main ()
{
    cin >> limita >> lungime;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> sir[indice]; }

    Backtracking(1 , 0 , 1);

    cout << total;
    cout.close(); cin.close();
    return 0;
}