#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;
LL n, k;
int big[1000006];
int main()
{
	freopen("light2.in", "r", stdin);
	freopen("light2.out", "w", stdout);
	cin >> n >> k;
	LL total = 0;
	vector<LL> v;
	for (int i = 0; i < k; ++i)
	{
		LL x; cin >> x;
		big[x]++;
	}
	for (int i = 2; i <= 1000000; ++i) if (big[i] % 2 == 1)
		v.push_back(i);
	k = v.size();
	for (int mask = 1; mask < (1 << k); ++mask)
	{
		LL p = 0;
		LL P = 1;
		int mare = 0;
		for (int i = 0; i < k; ++i)
			if (mask & (1 << i))
			{
				LL g = __gcd(P, v[i]);
				P = P * v[i]; P/=g;
				if (P > n) mare = 1;
				p++;
			}
		if (mare) continue;
		if (p % 2 == 1)
		{
			total += p * (n / P);
		}
		else
			total -= p * (n / P);
	}
	cout << total << '\n';
	return 0;
}