stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

using namespace std;

using ll = long long;



template<class T> inline bool chmin(T& a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



template<class T> inline bool chmax(T& a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}

struct Unionfind {

    vector<int> par;



    Unionfind(int n) : par(n) {

        for(int i = 0; i < n; ++i) par[i] = i;

    }



    int root(int x) {

        if(par[x] == x) return x;

        return par[x] = root(par[x]);

    }



    void unite(int x, int y) {

        int rx = root(x);

        int ry = root(y);

        if(rx == ry) return;

        par[rx] =ry;

    }



    bool same(int x, int y) {

        int rx = root(x);

        int ry = root(y);

        return rx == ry;

    }

};



int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);



    int n;

    cin >> n;



    const int num = 1000000;

    vector<int> cnt(num+1, 0);

    vector<int> a(n);



    int a_1_cnt = -1;

    rep(i, n) {

        cin >> a[i];

        if(a[i] == 1) ++a_1_cnt;

        if(a_1_cnt >= 2) {

            cout << 0 << endl;

            return 0;

        }



        for(int j = a[i]; j <= num; j += a[i]) ++cnt[j];

    }



    int ans = 0;

    rep(i, n) {

        if(cnt[a[i]] == 1) ++ans;

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0887714557796144x):
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

using namespace std;

using ll = long long;



template<class T> inline bool chmin(T& a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



template<class T> inline bool chmax(T& a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}

struct Unionfind {

    vector<int> par;



    Unionfind(int n) : par(n) {

        for(int i = 0; i < n; ++i) par[i] = i;

    }



    int root(int x) {

        if(par[x] == x) return x;

        return par[x] = root(par[x]);

    }



    void unite(int x, int y) {

        int rx = root(x);

        int ry = root(y);

        if(rx == ry) return;

        par[rx] =ry;

    }



    bool same(int x, int y) {

        int rx = root(x);

        int ry = root(y);

        return rx == ry;

    }

};



int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);



    int n;

    cin >> n;



    const int num = 1000000;

    vector<int> cnt(num+1, 0);

    vector<int> a(n);



    rep(i, n) {

        cin >> a[i];

        if(cnt[a[i]] != 0) {

            cnt[a[i]] = 10;

            continue;

        }

        for(int j = a[i]; j <= num; j += a[i]) ++cnt[j];

    }



    int ans = 0;

    rep(i, n) {

        if(cnt[a[i]] == 1) ++ans;

    }

    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define REP(i, n) for(int (i)=0;(i)<(n);++(i))

#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))

#define ALL(v) (v).begin(),(v).end()



#define MOD 1000000007



using namespace std;



typedef long long ll;



vector<ll> divisor(ll n) {

  vector<ll> ret;

  for(ll i = 1; i * i <= n; i++) {

    if(n % i == 0) {

      ret.push_back(i);

      if(i * i != n) ret.push_back(n / i);

    }

  }

  sort(begin(ret), end(ret));

  return (ret);

}



int main()

{

    ll N;

    cin >> N;

    vector<ll> A(N);

    REP(i, N)

    {

        cin >> A[i];

    }



    sort(ALL(A));



    const ll maxA = 1000000;

    ll ans = 0;

    vector<bool> isA(maxA + 1, false);

    REP(i, N)

    {

        if (i - 1 >= 0 && A[i] == A[i - 1])

        {

            isA[A[i]] = true;

            continue;

        }

        if (i + 1 < N && A[i] == A[i + 1])

        {

            isA[A[i]] = true;

            continue;

        }

        bool flag = true;

        vector<ll> divV = divisor(A[i]);

        divV.pop_back();

        REPV(it, divV)

        {

            if (isA[*it])

            {

                flag = false;

                break;

            }

        }

        if (flag)

        {

            ans++;

        }

        isA[A[i]] = true;

    }



    cout << ans << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.1243040673058062x):
#include <bits/stdc++.h>



#define REP(i, n) for(int (i)=0;(i)<(n);++(i))

#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))

#define ALL(v) (v).begin(),(v).end()



#define MOD 1000000007



using namespace std;



typedef long long ll;



int main()

{

    ll N;

    cin >> N;

    vector<ll> A(N);

    map<ll, ll> countA;

    REP(i, N)

    {

        cin >> A[i];

        countA[A[i]]++;

    }



    sort(ALL(A));

    ll aMax = A[N - 1];

    vector<bool> isCalced(aMax + 1, false), sieve(aMax + 1, true);

    ll ans = 0;

    REP(i, N)

    {

        if (isCalced[A[i]])

        {

            continue;

        }

        isCalced[A[i]] = true;

        if (sieve[A[i]])

        {

            if (countA[A[i]] == 1)

            {

                ans++;

            }

            ll k = 2;

            while(A[i] * k <= aMax)

            {

                sieve[A[i] * k] = false;

                k++;

            }

        }

    }



    cout << ans << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define vl vector<ll>

#define rep(i, n) for (int i = 0; i < (n); ++i)



int main() {

    ll N;

    cin >> N;



    vl A(N);

    vl E(1e6+5, 0);

    rep(i, N) {

        cin >> A[i];

    }



    sort(A.begin(), A.end());



    rep(i, N) {

        E[A[i]] = i+1;

    }



    int ans = 0;

    rep(i, N) {

        // cout << "i : " << i << "  A[i] : " << A[i] <<  endl;

        bool ok = true;

        if (i < N-1 && A[i] == A[i+1]) continue;

        if (i > 0 && A[i] == A[i-1]) continue;

        int max_j = floor(sqrt(A[i]));

        for (int j = 1; j <= min(max_j, 1000); ++j) {

            if (A[i] % j == 0) {

                // cout << "j : " << j << endl;

                // auto itr_1 = find(A.begin(), A.end(), j);

                // if (itr_1 != A.end() && itr_1 - A.begin() != i) {

                if (E[j] && E[j]-1 != i) {

                    ok = false;

                    break;

                }

                // auto itr_2 = find(A.begin(), A.end(), A[i]/j);

                // if (itr_2 != A.end() && itr_2 - A.begin() != i) {

                if (E[A[i]/j] && E[A[i]/j]-1 != i) {

                    ok = false;

                    break;

                }

            }

        }

        if (ok) {

            // cout << A[i] << endl;

            ans++;

        }

    }



    cout << ans << endl;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 9.339737199537584x):
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define vl vector<ll>

#define rep(i, n) for (int i = 0; i < (n); ++i)



int main() {

    int N;

    cin >> N;



    vector<int> A(N);

    rep(i, N) {

        cin >> A[i];

    }

    sort(A.begin(), A.end());



    vector<bool> dp(A[N-1]+1, true);

    int itr = 0;

    for (int i = 0; i < N; ++i) {

        if (!dp[A[i]]) continue;

        for (int j = 2; j*A[i] <= A[N-1]; ++j) {

            dp[j*A[i]] = false;

        }

    }



    int ans = 0;

    rep(i, N) {

        if (i < N-1 && A[i] == A[i+1]) {

            dp[A[i]] = false;

        }

        if (dp[A[i]]) ans++;

    }



    // rep(i, A[N-1]+1) {

    //     if (dp[i]) cout << i << " " << 1 << endl;

    //     else cout << i << " " << 0 << endl;

    // }



    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,x,n) for(int i = x; i < (int)(n); i++)

#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)

using namespace std;

typedef long long ll;

typedef unsigned long long u_ll;

typedef pair<int, int> pair_;

const long double PI = (acos(-1));

const int INF = 1001001001;

const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};

ll mod = 1000000007;

int main(){

    int n;

    cin >> n;

    priority_queue<int> q;

    vector<int> a(n);

    rep(i, 0, n) {

        cin >> a[i];

    }

    sort(a.begin(), a.end());

    int aamax=1000002;

    vector<int> aa(1000002, 0);

    rep(i, 0, n){

        for(int j=a[i]; j< a[n-1]+1;j+=a[i]) aa[j]++;

    }

    int cnt=0;

    rep(i, 0, n) if(aa[a[i]]==1) cnt++; 



    cout << cnt;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.069566375167813x):
#include <bits/stdc++.h>

#define rep(i,x,n) for(int i = x; i < (int)(n); i++)

#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)

using namespace std;

typedef long long ll;

typedef unsigned long long u_ll;

typedef pair<int, int> pair_;

const long double PI = (acos(-1));

const int INF = 1001001001;

const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};

ll mod = 1000000007;

int main(){

    int n;

    cin >> n;

    priority_queue<int> q;

    vector<int> a(n);

    rep(i, 0, n) cin >> a[i];

    sort(a.begin(), a.end());

    int aamax=a[n-1]+1;

    vector<int> aa(aamax, 0);

    rep(i, 0, n){

        if(aa[a[i]]!=0){

            aa[a[i]]=2;

            continue;

        }

        for(int j=a[i]; j< aamax;j+=a[i]) aa[j]++;

    }

    int cnt=0;

    rep(i, 0, n) if(aa[a[i]]==1) cnt++; 



    cout << cnt;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,x,n) for(int i = x; i < (int)(n); i++)

#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)

using namespace std;

typedef long long ll;

typedef unsigned long long u_ll;

typedef pair<int, int> pair_;

const long double PI = (acos(-1));

const int INF = 1001001001;

const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};

ll mod = 1000000007;

int main(){

    int n;

    cin >> n;

    priority_queue<int> q;

    vector<int> a(n);

    rep(i, 0, n) {

        cin >> a[i];

    }

    sort(a.begin(), a.end());

    int aamax=1000002;

    vector<int> aa(1000002, 0);

    rep(i, 0, n){

        for(int j=a[i]; j< a[n-1]+1;j+=a[i]) aa[j]++;

    }

    int cnt=0;

    rep(i, 0, n) if(aa[a[i]]==1) cnt++; 



    cout << cnt;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.9322490903665546x):
#include <bits/stdc++.h>

#define rep(i,x,n) for(int i = x; i < (int)(n); i++)

#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)

using namespace std;

typedef long long ll;

typedef unsigned long long u_ll;

typedef pair<int, int> pair_;

const long double PI = (acos(-1));

const int INF = 1001001001;

const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};

ll mod = 1000000007;

int main(){

    const int MAX_SIZE=1000005;

    bool num[MAX_SIZE];

    rep(i, 0, MAX_SIZE) num[i]=false;

    int n;

    cin >> n;

    vector<int> a(n);

    rep(i, 0, n) cin >> a[i];

    sort(a.begin(), a.end());

    int cnt=0;

    //エラトステネスの篩

    rep(i, 0, n){

        if(num[a[i]]==true) continue;

        //重複判定、昇順なのでこれでOK

        if(!(i<n-1&&a[i]==a[i+1])) cnt++;



        for(int j = a[i]; j < MAX_SIZE; j+=a[i]) num[j]=true;

    }

    cout << cnt;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,x,n) for(int i = x; i < (int)(n); i++)

#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)

using namespace std;

typedef long long ll;

typedef unsigned long long u_ll;

typedef pair<int, int> pair_;

const long double PI = (acos(-1));

const int INF = 1001001001;

const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};

ll mod = 1000000007;

int main(){

    int n;

    cin >> n;

    priority_queue<int> q;

    vector<int> a(n);

    rep(i, 0, n) cin >> a[i];

    sort(a.begin(), a.end());

    int aamax=1000002;

    vector<int> aa(aamax, 0);

    rep(i, 0, n){

        if(aa[a[i]]!=0){

            aa[a[i]]=2;

            continue;

        }

        for(int j=a[i]; j< aamax;j+=a[i]) aa[j]++;

    }

    int cnt=0;

    rep(i, 0, n) if(aa[a[i]]==1) cnt++; 



    cout << cnt;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.091744264443224x):
#include <bits/stdc++.h>

#define rep(i,x,n) for(int i = x; i < (int)(n); i++)

#define rep_ll(i,x,n) for(ll i = x; i < (ll)(n); i++)

using namespace std;

typedef long long ll;

typedef unsigned long long u_ll;

typedef pair<int, int> pair_;

const long double PI = (acos(-1));

const int INF = 1001001001;

const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};

ll mod = 1000000007;

int main(){

    const int MAX_SIZE=1000005;

    bool num[MAX_SIZE];

    rep(i, 0, MAX_SIZE) num[i]=false;

    int n;

    cin >> n;

    vector<int> a(n);

    rep(i, 0, n) cin >> a[i];

    sort(a.begin(), a.end());

    int cnt=0;

    //エラトステネスの篩

    rep(i, 0, n){

        if(num[a[i]]==true) continue;

        //重複判定、昇順なのでこれでOK

        if(!(i<n-1&&a[i]==a[i+1])) cnt++;



        for(int j = a[i]; j < MAX_SIZE; j+=a[i]) num[j]=true;

    }

    cout << cnt;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

const ll MOD = 1e9 + 7/*998244353*/;

const ll INF = 1LL << 60;

ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);

//

void fun(vector<ll>& vec, int a){

    for(int i = 1; i <= sqrt(a); i++){

        if(a % i == 0) {vec.push_back(i); vec.push_back(a / i);}

    }

}

int main(){

    int n;

    cin >> n;

    set<ll> nums;

    vector<ll> in(n);

    vector<bool> flag(1e6 + 1, false);

    vector<vector<ll>> divisor(n, vector<ll>());

    for(int i = 0; i < n; i++){

        int x; cin >> x;

        in[i] = x;

        if(flag[x]) nums.insert(x);

        flag[x] = true;

        fun(divisor[i], x);

    }

    ll ans = 0;

    for(int i = 0; i < n; i++){

        if(nums.count(in[i])) continue;

        bool bl = true;

        for(auto itr : divisor[i]){

            if(in[i] == itr) continue;

            if(flag[itr]) bl = false;

        }

        if(bl) ans++;

    }

    cout << ans;

}

// Faster C++ solution for the same problem (measured speedup: 1.131695976420394x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

const ll MOD = 1e9 + 7/*998244353*/;

const ll INF = 1LL << 60;

ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);

//

int main(){

    int n;

    cin >> n;

    vector<ll> nums(n);

    set<ll> appeared, reappeared;

    ll mx = 0;

    for(int i = 0; i < n; i++) {cin >> nums[i]; mx = max(mx, nums[i]);}

    vector<bool> available(mx + 1, true);

    for(int i = 0; i < n; i++){

        if(appeared.count(nums[i])) {reappeared.insert(nums[i]); continue;}

        appeared.insert(nums[i]);

        for(int j = 2; j <= mx / nums[i]; j++){

            //cout << nums[i] * j;

            available[nums[i] * j] = false;

        }

    }

    ll ans = 0;

    for(int i = 0; i < n; i++){

        if(reappeared.count(nums[i])) continue;

        if(available[nums[i]]) ans++;

    }

    //for(int i = 0; i <= mx; i++) cout << available[i] << " ";

    cout << ans;

}
// Slower C++ solution:
// D - Not Divisible

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define rep(i,n) for(int i=0;i<(int)(n);++i)



int main(){

	int N; cin>>N;

	vi A(N);

	vi l(1000000+1, 0);

	vi c(1000000+1, 0);

	// int mn = 0;

	int mx = 0;

	rep(i, N){

		int a; cin>>a;

		A[i] = a;

		// mn = min(mn, a);

		mx = max(mx, a);

		c[a]++;

	}



	for(int a:A){

		for(int i=a*2; i<=mx; i+=a) l[i] = 1;

	}



	int ans = 0;

	for(int a:A){

		if(!l[a] && c[a] <= 1) ans++;

	}

	cout<< ans <<endl;

}


// Faster C++ solution for the same problem (measured speedup: 9.32676125816357x):
// D - Not Divisible

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define rep(i,n) for(int i=0;i<(int)(n);++i)



int main(){

	int N; cin>>N;

	vi A(N);

	int mx = 0;

	rep(i, N){

		cin>>A[i];

		mx = max(mx, A[i]);

	}



	vi c(mx+1, 0);

	vi l(mx+1, 0);

	for(int a:A){

		c[a]++;

		for(int i=a*2; i<=mx; i+=a) l[i] = 1;

	}



	int ans = 0;

	for(int a:A) if(!l[a] && c[a] <= 1) ans++;

	cout<< ans <<endl;

}
// Slower C++ solution:
// D - Not Divisible

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define rep(i,n) for(int i=0;i<(int)(n);++i)



int main(){

	int N; cin>>N;

	vi A(N);

	vi l(1000000+1, 0);

	vi c(1000000+1, 0);

	// int mn = 0;

	int mx = 0;

	rep(i, N){

		int a; cin>>a;

		A[i] = a;

		// mn = min(mn, a);

		mx = max(mx, a);

		c[a]++;

	}



	for(int a:A){

		for(int i=a*2; i<=mx; i+=a) l[i] = 1;

	}



	int ans = 0;

	for(int a:A){

		if(!l[a] && c[a] <= 1) ans++;

	}

	cout<< ans <<endl;

}


// Faster C++ solution for the same problem (measured speedup: 9.327502771830915x):
// D - Not Divisible

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define rep(i,n) for(int i=0;i<(int)(n);++i)



int main(){

	int N; cin>>N;

	vi A(N);

	int mx = 0;

	rep(i, N){

		cin>>A[i];

		mx = max(mx, A[i]);

	}

	vi c(mx+1, 0);

	for(int a:A){

		for(int i=a; i<=mx; i+=a) c[i]++;

	}

	int ans = 0;

	for(int a:A) if(c[a] == 1) ans++;

	cout<< ans <<endl;

}
// Slower C++ solution:
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)

#define inf 1000000000000000000

#define mod 1000000007

#define mod2 998244353

#define pi acos(-1)

#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);

  cout << setprecision(15) << fixed;



  ll N; cin >> N;

  vector<ll> A(N);

  rep(i, N) cin >> A[i];



  map<ll, ll> Counter;

  vector<bool> ans(1000001, true);

  for (auto i : A) {

    Counter[i]++;

    if (Counter[i] > 1) continue;

    for (ll j = 2 * i; j < 1000001; j += i) {

      ans[j] = false;

    }

  }



  ll cnt = 0;

  for (auto i : A) {

    if (ans[i] && Counter[i] == 1) cnt++;

  }



  cout << cnt << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.259591383833742x):
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)

#define inf 1000000000000000000

#define mod 1000000007

#define mod2 998244353

#define pi acos(-1)

#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);

  cout << setprecision(15) << fixed;



  ll N; cin >> N;

  vector<ll> A(N);

  rep(i, N) cin >> A[i];

  set<ll> Used;

  vector<bool> ans(1000001, true);

  for (auto i : A) {

    if (Used.find(i) != Used.end()) {

      ans[i] = false;

      continue;

    }

    for (ll j = 2 * i; j < 1000001; j += i) {

      ans[j] = false;

    }

    Used.insert(i);

  }



  ll cnt = 0;

  for (auto i : A) {

    if (ans[i]) cnt++;

  }



  cout << cnt << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(v) v.begin(), v.end()

//#define MOD 1000000007

const int INF = 1LL<<30;



int cnt[1010101];

bool ok[1010101];



int main() {

    int n;

    cin>>n;

    vector<int> a(n);

    rep(i,n) cin>>a[i];



    rep(i,n) cnt[a[i]]++;

    for(int x=1;x<1010101;x++) ok[x]=true;

    for(int x=1;x<1010101;x++){

        if(0<cnt[x]){

            if(1<cnt[x]) ok[x]=false;

            for(int x2=x*2;x2<1010101;x2+=x) ok[x2]=false;

        }

    }



    int ans=0;

    rep(i,n){

        if(ok[a[i]]) ans++;

    }



    cout<<ans<<endl;



}

// Faster C++ solution for the same problem (measured speedup: 2.9157105670846106x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(v) v.begin(), v.end()

#define MOD 1000000007

const int INF = 1LL<<30;



int main(){

    int n;

    cin>>n;

    vector<int> a(n);

    set<int> b;

    rep(i,n){

        cin>>a[i];

        b.insert(a[i]);

    }



    sort(all(a));

    vector<bool> ok(1000010,true);

    rep(i,n-1){

        if(a[i]==a[i+1]) ok[a[i]]=false;

    }

    

    for(auto x : b){

        for(int j=2*x;j<1000010;j+=x) ok[j]=false;

    }

    



    int ans=0;

    for(auto x : b){

        if(ok[x]){

            ans++;

            //cout<<a[i]<<endl;

        }

    }



    cout<<ans<<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(v) v.begin(), v.end()

//#define MOD 1000000007

const int INF = 1LL<<30;



int cnt[1010101];

bool ok[1010101];



int main() {

    int n;

    cin>>n;

    vector<int> a(n);

    rep(i,n) cin>>a[i];



    rep(i,n) cnt[a[i]]++;

    for(int x=1;x<1010101;x++) ok[x]=true;

    for(int x=1;x<1010101;x++){

        if(0<cnt[x]){

            if(1<cnt[x]) ok[x]=false;

            for(int x2=x*2;x2<1010101;x2+=x) ok[x2]=false;

        }

    }



    int ans=0;

    rep(i,n){

        if(ok[a[i]]) ans++;

    }



    cout<<ans<<endl;



}

// Faster C++ solution for the same problem (measured speedup: 6.231547370437925x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(v) v.begin(), v.end()

#define MOD 1000000007

const int INF = 1LL<<30;



int main(){

    int n;

    cin>>n;

    vector<int> a(n);

    rep(i,n) cin>>a[i];



    sort(all(a));

    vector<bool> ok(1000010,false);



    rep(i,n){

        if(ok[a[i]]) continue;

        for(int j=2*a[i];j<=a[n-1];j+=a[i]) ok[j]=true;

        if(a[i]==a[i+1]) ok[a[i]]=true;

    }



    int ans=0;

    rep(i,n){

        if(!ok[a[i]]){

            ans++;

            //cout<<a[i]<<endl;

        }

    }



    cout<<ans<<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(v) v.begin(), v.end()

#define MOD 1000000007

const int INF = 1LL<<30;



int main(){

    int n;

    cin>>n;

    vector<int> a(n);

    set<int> b;

    rep(i,n){

        cin>>a[i];

        b.insert(a[i]);

    }



    sort(all(a));

    vector<bool> ok(1000010,true);

    rep(i,n-1){

        if(a[i]==a[i+1]) ok[a[i]]=false;

    }

    

    for(auto x : b){

        for(int j=2*x;j<1000010;j+=x) ok[j]=false;

    }

    



    int ans=0;

    for(auto x : b){

        if(ok[x]){

            ans++;

            //cout<<a[i]<<endl;

        }

    }



    cout<<ans<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.137231123275993x):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)

#define all(v) v.begin(), v.end()

#define MOD 1000000007

const int INF = 1LL<<30;



int main(){

    int n;

    cin>>n;

    vector<int> a(n);

    rep(i,n) cin>>a[i];



    sort(all(a));

    vector<bool> ok(1000010,false);



    rep(i,n){

        if(ok[a[i]]) continue;

        for(int j=2*a[i];j<=a[n-1];j+=a[i]) ok[j]=true;

        if(a[i]==a[i+1]) ok[a[i]]=true;

    }



    int ans=0;

    rep(i,n){

        if(!ok[a[i]]){

            ans++;

            //cout<<a[i]<<endl;

        }

    }



    cout<<ans<<endl;

}