stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

using namespace std;

const int MAXn = 1e5 + 10;

vector<int> g[MAXn];

int n, odd[MAXn], even[MAXn];



int dfs(int v, int par) {

	if (g[v].size() == 1 && par != 0)

		return 1;

	int cnt = 0;

	for (int i = 0; i < g[v].size(); i++)

		if (g[v][i] != par) {

			cnt += dfs(g[v][i], v);

			

		}

	if (cnt > 1) {

		cout << "First";

		exit(0);

	}

	if (cnt == 1) 

		return 0;

	if (par == 0) {

		cout << "First";

		exit(0);

	}

		

	return 1;

}





int main() {

	cin >> n;

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

		int u, v;

		cin >> u>> v;

		g[u].push_back(v);

		g[v].push_back(u);

	}

	dfs(1, 0);

	

	cout << "Second";

	

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

using namespace std;

#define MAXN 100000

int n,u,v,F;

vector<int> G[MAXN+5];

int dfs(int x,int fa){

	int p=0;

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

		int nxt=G[x][i];

		if(nxt==fa)continue;

		p+=dfs(nxt,x);

	}

	if(p>=2)F=1;

	return p^1;

}

int main()

{

	scanf("%d",&n);

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

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

		G[u].push_back(v);

		G[v].push_back(u);

	}

	if(dfs(1,0)==0&&!F)printf("Second\n");

	else printf("First");

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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");

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem: