#include <fstream>
#include <algorithm>

using namespace std;

constexpr int kMaxK = 22;

int value[kMaxK];
int logarithm[1 << kMaxK];

long long gcd(const long long a, const long long b) {
	if (b == 0LL) {
		return a;
	}
	return gcd(b, a - a / b * b);
}

int main() {
	ifstream cin("light2.in");
	ofstream cout("light2.out");
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	long long n; int k;
	cin >> n >> k;
	
	for (int i = 0; i < k; i += 1) {
		cin >> value[i];
	}
	sort(value, value + k);
	reverse(value, value + k);

	const int mask_limit = (1 << k);
	for (int i = 2; i < mask_limit; i += 1) {
		logarithm[i] = logarithm[i >> 1] + 1;
	}
	long long answer = 0LL;
	for (int i = 1; i < mask_limit; i += 1) {
		int bit_count = 0;
		long long lcm = 1LL;
		for (int j = i; j; j &= (j - 1)) {
			const int bit = logarithm[j & -j];
			lcm = (lcm * value[bit]) / gcd(lcm, value[bit]);
			if (lcm > n) {
				break;
			}
			bit_count += 1;
		}
		if (lcm <= n) {
			if (bit_count & 1) {
				answer += (n / lcm) << (bit_count - 1);
			} else {
				answer -= (n / lcm) << (bit_count - 1);
			}
		}
	}
	cout << answer << '\n';
	return 0;
}