#include <cstdio>
#include <cmath>
#include <bitset>

using namespace std;

FILE *f=fopen("light2.in", "r");
FILE *g=fopen("light2.out", "w");


long long n, k, v[230];
bitset <11000000> w;

void read()
{
	fscanf(f, "%lld%lld", &n, &k);
	for (int i=1; i<=k; ++i)
		fscanf(f, "%lld", &v[i]);
}

void program()
{
	long long sol = n;  
	for (int i = 1; i < (1 << k); i++) 
	{     
		long long nr = 0, prod = 1;    
		int ok=1;
		for (int j = 0; j < k; j++)        
			if ((1 << j) & i) 
			{       
				if (n/prod<v[j+1])
				{
					prod=0;
					ok=0;
					break;
				}
				prod = 1LL * prod * v[j + 1]; 
				nr++;     
			}    

		if (ok)
		{

			float plm=static_cast <float> (nr -1);
			long long p2= static_cast <long long> (pow(2, plm));
			
			if (nr % 2) nr = -1; 
			else nr=1;
			
			sol = sol + 1LL * nr * n / prod *p2; 
		}
		
	}
		
	fprintf(g, "%lld", n-sol);
}




int main()
{
	read();
	
	if (n>9999999)
		program();
	else
	{
		for (int i=1; i<=k; ++i)
		{
		
			for (long long j=v[i]; j<=n; j+=v[i])
				w.set(j, 1-w[j]);
		}
		
		long long nr=0;
		for (long long l=1; l<=n; ++l)
			if (w[l]==1) 
			{
				++nr;
			}
		
		fprintf(g, "%lld", nr);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}