//真tm是乱搞 但是（乱搞的）思想很重要
解：大概就是记忆化搜索，但是原数据范围太大，不可能记下所有的情况的答案，于是我们就在记下小范围内的答案，当dfs落入这个记忆范围后，就不进一步搜索，直接返回记下来的答案，这样就起到了优化的效果，但是并不知道这种复杂度是怎么算的。然而我们由大到小排序，使得状态总可以很快地落入记忆化的范围。
dfs(n,now)代表[1..n]内不会被a[now]...a[k-1]整除的数有多少，那么答案就是dfs(n,0)。
转移关系如下:dfs(n,now)=dfs(n,now+1)-dfs(n/a[i],now+1)
之所以要-dfs(n/a[i],now+1)是为了避免一个数被重复减多次，能被整除的数整除后按大小排列一定是1,2,3,...,n/a[i],如果能被后面的数整除，就将其减去，也就是减dfs(n/a[i],now+1).
/*
某学长的讲解：
给K个两两互素的数，问[1,N]中有多少个数不被K个数里任何一个数整除。
假设N比较小，可以这样做。dp[i][j]表示前i个素数，范围在[1,j]里的答案。那么，方程转移dp[i][j]=dp[i-1][j]+dp[i-1][j/p[i]]。（具体为啥仔细想想素数的性质，或者按照分解素数方法来想）
N很大，怎么办。当N<10万，20万，30万可以直接dp做。当N很大的时候，注意到j/p[i]，是log级别的，情况数并不会很多。所以可以设一个M，比如M=20万，当j<=M的时候，记忆化，O(1)查询，当j>M的时候，dfs搜索。
这题不好分析复杂度。可以发现，P数组里元素顺序是不影响答案的，我们可以把P从小到大排序，这样j/p[i]中的p[i]会更大，搜索起来更快。（当然，这只是小优化）。
不会写的话看代码。
*/
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; const int MAXN=; long long n;
int k;
int a[];
long long f[MAXN][]; bool cmp(int a,int b){
return a>b;
} long long dfs(long long n,int now){
if (now>=k || n==) return n;
if (n<MAXN && f[n][now]>=) return f[n][now];
long long tmp=dfs(n,now+)-dfs(n/a[now],now+);
if (n<MAXN) f[n][now]=tmp;
return tmp;
} int main(){
scanf("%lld%d",&n,&k);
for (int i=;i<MAXN;i++){
for (int j=;j<k;j++){
f[i][j]=-;
}
}
for (int i=;i<k;i++) scanf("%d",&a[i]);
sort(a,a+k,cmp);
printf("%lld\n",dfs(n,)); //printf("I64d printed\n");
return ;
}
/*
20 3
2 3 5 50 2
15 8
*/