#include<stdio.h>
using namespace std;

typedef struct
{
	long long val;
	int nr;
	long long inm;
} valori;

long long n;
short int k;
long long nr;
valori B[100000];
long int bacc = 0;

void citire(void)
{
	long long a;
	FILE *f = fopen("light2.in","r");
	
	fscanf(f,"%lld",&n);
	fscanf(f,"%d",&k);
	for(int i=1;i<=k;i++)
	{
		fscanf(f,"%lld",&B[i].val);
		B[i].nr = 1;
		B[i].inm = 1;
	}
	bacc = k;
	
	fclose(f);
}

int inc(int i,int j)
{
	long int l;
	for(l=1;l<=bacc && B[l].val != i*j;l++);
	return l;
}

void calc(void)
{
	FILE *f = fopen("light2.out","w");
	
	nr = 0;
	
	for(int i=1;i<=bacc;i++)
		if(!(B[i].nr%2))
			nr -= B[i].inm*(n/B[i].val);
		else
			nr += B[i].inm*(n/B[i].val);	

	fprintf(f,"%lld\n",nr);
/*
	for(int i=1;i<=bacc;i++)
		fprintf(f,"%7lld ",B[i].val);
	fprintf(f,"\n");
	for(int i=1;i<=bacc;i++)
		fprintf(f,"%7lld ",B[i].nr);
	fprintf(f,"\n");
	for(int i=1;i<=bacc;i++)
		fprintf(f,"%7lld ",B[i].inm);
*/
		
	fclose(f);
}

void prel(void)
{
	long int l = 0;
	long int i = 0;
	long int j = 0;
	long int nri = 0;
	long int nrj = 0;
	long int nr1;
	long int nri2 = 1;
	int gata = 1;
	bacc = k;
	for(i=1;i<=k;i++)
		for(j=1;j<=k;j++)
			if(i!=j && !(B[i].val%B[j].val))
			{
				B[i].nr ++;
			}
	while(gata)
	{
	gata = 0;
	nrj = bacc;
	for(i=nri2;i<=nri;i++)
		for(j=nri+1;j<=nrj;j++)
			if(!(B[j].val%B[i].val))
			{
				B[j].nr ++;
				if(B[j].nr%2 && B[j].nr>1)
					nr -= B[j].inm;
			}
	for(i=nri+1;i<=nrj;i++)
		for(j=nri+1;j<=nrj;j++)
			if(i!=j && B[i].val*B[j].val<=n && B[i].val%B[j].val && B[j].val%B[i].val)
			{
			  if(inc(B[i].val,B[j].val)>bacc)
			  {
				B[++bacc].val = B[i].val*B[j].val;
				if(B[nri].inm < 2)
				  B[bacc].inm = 2;
				else
				  B[bacc].inm = B[nri].inm*B[nri].inm;
				gata ++;
			  }
			}
	nri2 = nri + 1;
	nri = nrj;
	}
}

int main()
{
	citire();
	prel();
	calc();
		
	return 0;
}