#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int>v(n+1,0);
    for(int i=0;i<m;i++){
        int a;
        cin>>a;
        v[a]++;
    }
    vector<int>ans(n+1,1);
    for(int i=n;i>=1;i--){
        int tmp=0;
        for(int j=i;j<=n;j+=i){
            tmp+=ans[j];
        }
        if(tmp%2!=v[i])ans[i]=0;
    }
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=ans[i+1];
    }
    cout<<n-sum<<endl;
    return 0;
}