stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;



#define MAXN 100000

int N,Root;

vector<int> G[MAXN+5];



int dfs(int u,int fa){//0黑 1百 -1必胜

	if(u!=Root&&G[u].size()==1)

		return 0;

	int cnt=0;

	for(int i=0;i<int(G[u].size());i++){

		int v=G[u][i];

		if(v!=fa){

			int tmp=dfs(v,u);

			if(tmp==-1)

				return -1;

			cnt+=tmp==0;

		}

	}

	if(cnt>=2)

		return -1;

	if(u==Root)

		return cnt!=1;

	return cnt==1;

}



int main(){

	scanf("%d",&N);

	for(int i=1;i<=N-1;i++){

		int u,v;

		scanf("%d%d",&u,&v);

		G[u].push_back(v);

		G[v].push_back(u);

	}

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

		if(G[i].size()==1){

			Root=i;

			break;

		}

	}

	puts(dfs(Root,-1)?"First":"Second");

}


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

using namespace std;

int n,head[100005],cnt,in[100005],flag,vis[100005];

struct edge{int to,next;

}e[200005];

void add(int x,int y)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	head[x]=cnt++;

}

void dfs(int u,int pre)

{

	int tot=0;

	for(int i=head[u];i;i=e[i].next)

	{

		if(e[i].to==pre)continue;

		dfs(e[i].to,u);

	}

	if(u==1&&!vis[u])flag=1;

	if(!vis[u])

	{

		vis[u]++;vis[pre]++;

	}

	if(vis[u]!=1)flag=1;

}

int main()

{

	flag=0;cnt=1;

	scanf("%d",&n);

	for(int i=1;i<n;++i)

	{

		int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);

	}

	dfs(1,0);



	if(flag)puts("First");

	else puts("Second");

  return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;



#define MAXN 100000

int N,Root;

vector<int> G[MAXN+5];



int dfs(int u,int fa){//0黑 1百 -1必胜

	if(u!=Root&&G[u].size()==1)

		return 0;

	int cnt=0;

	for(int i=0;i<int(G[u].size());i++){

		int v=G[u][i];

		if(v!=fa){

			int tmp=dfs(v,u);

			if(tmp==-1)

				return -1;

			cnt+=tmp==0;

		}

	}

	if(cnt>=2)

		return -1;

	if(u==Root)

		return cnt!=1;

	return cnt==1;

}



int main(){

	scanf("%d",&N);

	for(int i=1;i<=N-1;i++){

		int u,v;

		scanf("%d%d",&u,&v);

		G[u].push_back(v);

		G[v].push_back(u);

	}

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

		if(G[i].size()==1){

			Root=i;

			break;

		}

	}

	puts(dfs(Root,-1)?"First":"Second");

    return 0;

}


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

using namespace std;

int n,head[100005],cnt,in[100005],flag,vis[100005];

struct edge{int to,next;

}e[200005];

void add(int x,int y)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	head[x]=cnt++;

}

void dfs(int u,int pre)

{

	int tot=0;

	for(int i=head[u];i;i=e[i].next)

	{

		if(e[i].to==pre)continue;

		dfs(e[i].to,u);

	}

	if(u==1&&!vis[u])flag=1;

	if(!vis[u])

	{

		vis[u]++;vis[pre]++;

	}

	if(vis[u]!=1)flag=1;

}

int main()

{

	flag=0;cnt=1;

	scanf("%d",&n);

	for(int i=1;i<n;++i)

	{

		int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);

	}

	dfs(1,0);



	if(flag)puts("First");

	else puts("Second");

  return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=100000;

vector<int> d[MAXN+5];

int n;

int dfs(int u,int fa)

{

	int res=0,v;

	for(int i=0;i<d[u].size();i++)

	{

		v=d[u][i];

		if(v!=fa)

			res+=dfs(v,u);

	}

	if(res>=2)

	{

		printf("First");

		exit(0);

	}

	else if(res==0)

		return 1;

	return 0;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n-1;i++)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		d[u].push_back(v);

		d[v].push_back(u);

	}

	if(dfs(1,0))

		printf("First");

	else

		printf("Second");

	return 0;

}


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

using namespace std;

int n,head[100005],cnt,in[100005],flag,vis[100005];

struct edge{int to,next;

}e[200005];

void add(int x,int y)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	head[x]=cnt++;

}

void dfs(int u,int pre)

{

	int tot=0;

	for(int i=head[u];i;i=e[i].next)

	{

		if(e[i].to==pre)continue;

		dfs(e[i].to,u);

	}

	if(u==1&&!vis[u])flag=1;

	if(!vis[u])

	{

		vis[u]++;vis[pre]++;

	}

	if(vis[u]!=1)flag=1;

}

int main()

{

	flag=0;cnt=1;

	scanf("%d",&n);

	for(int i=1;i<n;++i)

	{

		int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);

	}

	dfs(1,0);



	if(flag)puts("First");

	else puts("Second");

  return 0;

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

using namespace std;

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

 

typedef long long ll;

#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)

#define forn(i, n) forr(i, 0, n)

#define pb push_back

#define mp make_pair

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

#define DBG(x) cerr << #x << " = " << (x) << endl

#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl

#define esta(x,c) ((c).find(x) != (c).end())

#define RAYA cerr << "===============================" << endl

#define MAXN 2005

#define INF 1000000007



vector <int> divisores(int n)

{

	vector <int> ans;

	forr(i,1,sqrt(n)+1)

	{

		if(n%i == 0) 

		{

			ans.pb(i);

			if(i*i != n) ans.pb(n/i);

		}

		

	}

	sort(all(ans));

	return ans;

}



int main()

{ 

	FIN;

	

	#ifdef input

		//freopen("test1.txt", "r", stdin);

	#endif

	

	vector <int> visto(1000005,0);

	int n;

	cin >> n;

	vector <int> v(n);

	forn(i,n) cin >> v[i];

	forn(i,n) visto[v[i]]++;

	int ans = 0;

	forn(i,n)

	{

		vector <int> div = divisores(v[i]);

		bool d=false;

		visto[v[i]]--;

		for(auto u : div)

		{

			if(visto[u]>0) d=true;

		}

		if(d==true) ans++;

		visto[v[i]]++;

	}

	cout << n-ans << endl;

	return 0;

}


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

using namespace std;



int main() {

	int n;

	cin >> n;

	int ans=n;

	vector <int> v(n);

	map <int,int> m;

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

	{

		cin >> v[i];

		if(m[v[i]]==0) m[v[i]]=1;

		else m[v[i]]=2;

	}

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

	{

		for(int j=1; j<=sqrt(v[i]); j++)

		{

			if(v[i]%j==0)

			{

				if(m[j]>0)

				{

					ans-=1;

					break;

				}

				else

				{

					if(v[i]/j!=v[i])

					{

						if(m[v[i]/j]>0)

						{

							ans-=1;

							break;

						}

					}

					else if(m[v[i]]==2)

					{

						ans-=1;

						break;

					}

				}

			}

		}

	}

	if(m[1]==1) cout << 1 << endl;

	else

	{

		if(m[1]==2) cout << 0 << endl;

		else cout << ans << endl;

	}

	return 0;

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

using namespace std;

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

 

typedef long long ll;

#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)

#define forn(i, n) forr(i, 0, n)

#define pb push_back

#define mp make_pair

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

#define DBG(x) cerr << #x << " = " << (x) << endl

#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl

#define esta(x,c) ((c).find(x) != (c).end())

#define RAYA cerr << "===============================" << endl

#define MAXN 2005

#define INF 1000000007



vector <int> divisores(int n)

{

	vector <int> ans;

	forr(i,1,sqrt(n)+1)

	{

		if(n%i == 0) 

		{

			ans.pb(i);

			if(i*i != n) ans.pb(n/i);

		}

		

	}

	sort(all(ans));

	return ans;

}



int main()

{ 

	FIN;

	

	#ifdef input

		//freopen("test1.txt", "r", stdin);

	#endif

	

	vector <int> visto(1000005,0);

	int n;

	cin >> n;

	vector <int> v(n);

	forn(i,n) cin >> v[i];

	forn(i,n) visto[v[i]]++;

	int ans = 0;

	forn(i,n)

	{

		vector <int> div = divisores(v[i]);

		bool d=false;

		visto[v[i]]--;

		for(auto u : div)

		{

			if(visto[u]>0) d=true;

		}

		if(d==true) ans++;

		visto[v[i]]++;

	}

	cout << n-ans << endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.114941680065769x):
#include <iostream>



#include <deque>



#include <stdio.h>



#include <cstdio>



#include <algorithm>



#include<bits/stdc++.h>



#define pub push_back

#define puf push_front

#define pob pop_back

#define pof pop_front

#define sp <<" "

#define nw <<"\n"

#define ca "Case "<<tc++<<": "

#define IOS ios_base::sync_with_stdio(0);cin.tie(0)

#define ull unsigned LL

#define check cout<<"* ";

#define show_vector for(int q=0;q<v.size();q++){cout<<v[q]<<" ";}

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

#define N_MAX 26



const int inf=1<<30;

const long long int INF=1e10;

const int MOD=1e9+7;

const int maxn = 1e5+10;

int a[200005],b[1000005];



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;



int is_prime(int n)

{

    int coun;

     coun=0;

     if(n>1){

      for(int i=2;i*i<=n;i++){

        if( n%i==0 ){

            coun++;

          }

        }

      }

     if(n==1){

       coun=coun;

         }

    if(coun==0){

        return 1;

        }

    return 0;

}



int main()

{

    int n;

    vector<long long int>v;

    int cnt=0;

    cin>>n;



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

        int z;

        cin>>z;

        //if(is_prime(z)==1){

        //    cnt++;

        //    continue;

        //}

        v.pub(z);

    }

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



    int m=v.size();

    for(int i=0;i<m;i++)

	{

	    int r=2;

		for(int j=v[i];j<=v[m-1];j+=v[i])

		{

		    //cout<<j sp<<v[i] sp<<b[j] sp sp;

			b[j]++;

			//cout<<j sp<<v[i] sp<<b[j] nw;

		}

	}

	for(int i=0;i<m;i++)

	{

	    //cout<<b[v[i]] sp;

		if(b[v[i]]==1)

		cnt++;

	}

	cout<<cnt nw;

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

using namespace std;

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

 

typedef long long ll;

#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)

#define forn(i, n) forr(i, 0, n)

#define pb push_back

#define mp make_pair

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

#define DBG(x) cerr << #x << " = " << (x) << endl

#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl

#define esta(x,c) ((c).find(x) != (c).end())

#define RAYA cerr << "===============================" << endl

#define MAXN 2005

#define INF 1000000007

 

vector <int> divisores(int n)

{

	vector <int> ans;

	forr(i,1,sqrt(n)+1)

	{

		if(n%i == 0) 

		{

			ans.pb(i);

			if(i*i != n) ans.pb(n/i);

		}

		

	}

	sort(all(ans));

	return ans;

}

 

int main()

{ 

	FIN;

	

	#ifdef input

		//freopen("test1.txt", "r", stdin);

	#endif

	

	vector <int> visto(1000005,0);

	int n;

	cin >> n;

	vector <int> v(n);

	forn(i,n) cin >> v[i];

	forn(i,n) visto[v[i]]++;

	int ans = 0;

	forn(i,n)

	{

		vector <int> div = divisores(v[i]);

		bool d=false;

		visto[v[i]]--;

		for(auto u : div)

		{

			if(visto[u]>0) d=true;

		}

		if(d==true) ans++;

		visto[v[i]]++;

	}

	cout << n-ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.114941680065769x):
#include <iostream>



#include <deque>



#include <stdio.h>



#include <cstdio>



#include <algorithm>



#include<bits/stdc++.h>



#define pub push_back

#define puf push_front

#define pob pop_back

#define pof pop_front

#define sp <<" "

#define nw <<"\n"

#define ca "Case "<<tc++<<": "

#define IOS ios_base::sync_with_stdio(0);cin.tie(0)

#define ull unsigned LL

#define check cout<<"* ";

#define show_vector for(int q=0;q<v.size();q++){cout<<v[q]<<" ";}

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

#define N_MAX 26



const int inf=1<<30;

const long long int INF=1e10;

const int MOD=1e9+7;

const int maxn = 1e5+10;

int a[200005],b[1000005];



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;



int is_prime(int n)

{

    int coun;

     coun=0;

     if(n>1){

      for(int i=2;i*i<=n;i++){

        if( n%i==0 ){

            coun++;

          }

        }

      }

     if(n==1){

       coun=coun;

         }

    if(coun==0){

        return 1;

        }

    return 0;

}



int main()

{

    int n;

    vector<long long int>v;

    int cnt=0;

    cin>>n;



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

        int z;

        cin>>z;

        //if(is_prime(z)==1){

        //    cnt++;

        //    continue;

        //}

        v.pub(z);

    }

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



    int m=v.size();

    for(int i=0;i<m;i++)

	{

	    int r=2;

		for(int j=v[i];j<=v[m-1];j+=v[i])

		{

		    //cout<<j sp<<v[i] sp<<b[j] sp sp;

			b[j]++;

			//cout<<j sp<<v[i] sp<<b[j] nw;

		}

	}

	for(int i=0;i<m;i++)

	{

	    //cout<<b[v[i]] sp;

		if(b[v[i]]==1)

		cnt++;

	}

	cout<<cnt nw;

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

using namespace std;

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

 

typedef long long ll;

#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)

#define forn(i, n) forr(i, 0, n)

#define pb push_back

#define mp make_pair

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

#define DBG(x) cerr << #x << " = " << (x) << endl

#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl

#define esta(x,c) ((c).find(x) != (c).end())

#define RAYA cerr << "===============================" << endl

#define MAXN 2005

#define INF 1000000007



vector <int> divisores(int n)

{

	vector <int> ans;

	forr(i,1,sqrt(n)+1)

	{

		if(n%i == 0) 

		{

			ans.pb(i);

			if(i*i != n) ans.pb(n/i);

		}

		

	}

	sort(all(ans));

	return ans;

}



int main()

{ 

	FIN;

	

	#ifdef input

		//freopen("test1.txt", "r", stdin);

	#endif

	

	vector <int> visto(1000005,0);

	int n;

	cin >> n;

	vector <int> v(n);

	forn(i,n) cin >> v[i];

	forn(i,n) visto[v[i]]++;

	int ans = 0;

	forn(i,n)

	{

		vector <int> div = divisores(v[i]);

		bool d=false;

		visto[v[i]]--;

		for(auto u : div)

		{

			if(visto[u]>0) d=true;

		}

		if(d==true) ans++;

		visto[v[i]]++;

	}

	cout << n-ans << endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.136611642217351x):
#include<iostream>

#include<set>

using namespace std;



int a[200050];

int cnt[1000050];





int main(){



    int n;

    cin >> n;





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

        cin >> a[i];

        cnt[a[i]]++;

    }



    int ans = 0;

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

        bool val = true;

        for(int j=1;j*j<=a[i];j++){

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

                int r = j;

                int s = a[i]/j;



                if((a[i]==r && cnt[r]>1) || (a[i]!=r && cnt[r]>0)){

                    val = false;

                    break;

                }

                if((a[i]==s && cnt[s]>1) || (a[i]!=s && cnt[s]>0)){

                    val = false;

                    break;

                }

                /*if((a[i]==r && cnt[r]>1) || (a[i]==s && cnt[s]>1) || (a[i]!=r && a[i]!=s && (cnt[r]>0 || cnt[s]>0))){

                    val =  false;

                    break;

                }*/

            }

        }

        if(val)

            ans++;

    }



    cout << ans << endl;

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

using namespace std;

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

 

typedef long long ll;

#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)

#define forn(i, n) forr(i, 0, n)

#define pb push_back

#define mp make_pair

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

#define DBG(x) cerr << #x << " = " << (x) << endl

#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl

#define esta(x,c) ((c).find(x) != (c).end())

#define RAYA cerr << "===============================" << endl

#define MAXN 2005

#define INF 1000000007

 

vector <int> divisores(int n)

{

	vector <int> ans;

	forr(i,1,sqrt(n)+1)

	{

		if(n%i == 0) 

		{

			ans.pb(i);

			if(i*i != n) ans.pb(n/i);

		}

		

	}

	sort(all(ans));

	return ans;

}

 

int main()

{ 

	FIN;

	

	#ifdef input

		//freopen("test1.txt", "r", stdin);

	#endif

	

	vector <int> visto(1000005,0);

	int n;

	cin >> n;

	vector <int> v(n);

	forn(i,n) cin >> v[i];

	forn(i,n) visto[v[i]]++;

	int ans = 0;

	forn(i,n)

	{

		vector <int> div = divisores(v[i]);

		bool d=false;

		visto[v[i]]--;

		for(auto u : div)

		{

			if(visto[u]>0) d=true;

		}

		if(d==true) ans++;

		visto[v[i]]++;

	}

	cout << n-ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.136611642217351x):
#include<iostream>

#include<set>

using namespace std;



int a[200050];

int cnt[1000050];





int main(){



    int n;

    cin >> n;





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

        cin >> a[i];

        cnt[a[i]]++;

    }



    int ans = 0;

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

        bool val = true;

        for(int j=1;j*j<=a[i];j++){

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

                int r = j;

                int s = a[i]/j;



                if((a[i]==r && cnt[r]>1) || (a[i]!=r && cnt[r]>0)){

                    val = false;

                    break;

                }

                if((a[i]==s && cnt[s]>1) || (a[i]!=s && cnt[s]>0)){

                    val = false;

                    break;

                }

                /*if((a[i]==r && cnt[r]>1) || (a[i]==s && cnt[s]>1) || (a[i]!=r && a[i]!=s && (cnt[r]>0 || cnt[s]>0))){

                    val =  false;

                    break;

                }*/

            }

        }

        if(val)

            ans++;

    }



    cout << ans << endl;

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

using namespace std;

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

 

typedef long long ll;

#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)

#define forn(i, n) forr(i, 0, n)

#define pb push_back

#define mp make_pair

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

#define DBG(x) cerr << #x << " = " << (x) << endl

#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl

#define esta(x,c) ((c).find(x) != (c).end())

#define RAYA cerr << "===============================" << endl

#define MAXN 30005

#define INF 1000000007



vector <int> divisores(int n)

{

	vector <int> ans;

	for(int i=1; i<sqrt(n)+1; i++)

	{

		if(n%i==0)

		{

			ans.push_back(i); // n/i tambien es divisor y es mayor a raiz de n 

			if(i*i != n) ans.pb(n/i);

		}

	}

	

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

	//(reverse(ans.begin(),ans.end());

	return ans;

}





int main()

{ 

	FIN;

	

	#ifdef input

		freopen("T3.txt", "r", stdin);

	#endif

	

	int n;

	cin >> n;

	vector <int> v(n);

	for(int i=0; i<n; i++) cin >> v[i];

	

	vector <int> cont(1000005,0);

	

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

	{

		cont[v[i]]++;

	}

	

	int ans=0;

	

	//O(n^2) 4*10^10 operaciones

	//O(n*(n+1)/2) --> O(n^2)

	

	//O(n*sqrt(MAXN)) --> 2*10^5*10^3 = 2*10^8 

	

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

	{

		bool d = true;

		vector <int> div = divisores(v[i]);

		//for(auto u : div) cout << u << " "; cout << endl;

		for(int j=0; j<div.size(); j++)

		{

			if(div[j]==v[i]) 

			{

				if(cont[div[j]]>1)

				{

					d=false;

				}

				continue;

			}

			if(cont[div[j]]>0) d=false;

		}

		if(d==true) ans++;

	}

	

	cout << ans << endl;

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.132735731083312x):
#include<iostream>

#include<set>

using namespace std;



int a[200050];

int cnt[1000050];





int main(){



    int n;

    cin >> n;





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

        cin >> a[i];

        cnt[a[i]]++;

    }



    int ans = 0;

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

        bool val = true;

        for(int j=1;j*j<=a[i];j++){

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

                int r = j;

                int s = a[i]/j;



                if((a[i]==r && cnt[r]>1) || (a[i]!=r && cnt[r]>0)){

                    val = false;

                    break;

                }

                if((a[i]==s && cnt[s]>1) || (a[i]!=s && cnt[s]>0)){

                    val = false;

                    break;

                }

                /*if((a[i]==r && cnt[r]>1) || (a[i]==s && cnt[s]>1) || (a[i]!=r && a[i]!=s && (cnt[r]>0 || cnt[s]>0))){

                    val =  false;

                    break;

                }*/

            }

        }

        if(val)

            ans++;

    }



    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 REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))

#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))



constexpr int INF = 1e9;

//constexpr ll INF = 1LL<<61;

// constexpr ll mod = 1e9+7;



int main(){

  int N;

  cin >> N;

  vector<int> A(N);

  map<int, int> mp;

  int maxa = -1;

  REP(i, N){

    cin >> A[i];

    mp[A[i]]++;

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

  }

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

  vector<bool> dp((int)1e6+5, true);

  int ans = 0;

  REP(i, N){

    if(mp[A[i]] == 1 && dp[A[i]]){

      ans++;

    }

    if(dp[A[i]]){

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

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

      }

    }

  }

  cout << ans << endl;

  return 0;

}

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

using namespace std;

using ll = long long;



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

#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))

#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))



constexpr int INF = 1e9;

// constexpr ll INF = 1LL<<61;

constexpr ll mod = 1e9+7;



int main(){  

  int N;

  cin >> N;

  vector<int> A(N);

  map<int, int> mp;

  REP(i, N){

    cin >> A[i];

    mp[A[i]]++;

  }

  

  int ans = 0;

  REP(i, N){

    if(mp[A[i]] >= 2) continue;

    if(A[i] != 1 && mp[1]) continue;

    bool flag = true;

    for(int x = 2; x*x <= A[i]; x++){

      if(A[i] % x != 0) continue;

      if(mp[A[i]/ x]) flag = false;

      if(mp[x]) flag = false;

    }

    if(flag) ans++;

  }

  cout << ans << endl;

  return 0;

}