Language: C++


// Problem : D - Not Divisible
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define hell1 1000000007
#define hell2 1000000009
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ll long long
#define ld long double 
#define no_of_digits(n) floor(log10(n)) + 1
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define see(x) cout << #x << "=" << x << endl;
#define see2(x, y) cout << #x << "=" << x << "\t" << #y << "=" << y << endl;
#define see3(x, y, z) cout << #x << "=" << x << "\t" << #y << "=" << y << "\t" << #z << "=" << z << endl;
#define INF 1e9+5
#define LL_MAX 1e18+5

using namespace std;

const ld PI = acos((ld)-1);
 
ll modmult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
ll modmultbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=modmultbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;}
ll modadd(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
ll modsub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = modmult(r,n,p); n = modmult(n,n,p);} return r;}
ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}

int isPowerof2(ll x) { return (x && !(x & (x-1))); } 

ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; } 

bool isPerfectSquare(long double x) {long double sr = sqrt(x); return ((sr - floor(sr)) == 0); }
 
bool boundary(ll i,ll j,ll n, ll m){return (i>=0 && i<n && j>=0 &&  j<m);} //matrix boundary checking

ll ceil(const ll &a, const ll &b){return (a - 1)/b + 1;}
ll lcm(ll a, ll b){return a/__gcd(a, b)*b;}

 
string alpha="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

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

// cout << fixed for removing e notation
 
bool comp2(const pair<int, int>&a, const pair<int, int>&b)
{
    if(a.second < b.second)
        return true;
    else if(a.second == b.second)
    {
        if(a.fi > b.fi) return true;
        else return false;
    }
    else return false;
}
 
bool prime[10000005];
void SieveOfEratosthenes(int n) 
{
    memset(prime, true, sizeof(prime)); 
    prime[0] = prime[1] = 0;
    for (int p=2; p*p<=n; p++) 
    {
        if (prime[p] == true) 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
    }
}

int main()
{
	int n;
	cin >> n;
	
	int a[n];
	map<int, int>mp;
	set<int>st;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		st.insert(a[i]);
		mp[a[i]]++;
	}
	
	int ok = 0;
	for(auto x: mp)
	{
		if(x.se == 1)
		{
			ok = 1;
			break;
		}
	}
	
	if(!ok)
	{
		cout << 0 << "\n";
		return 0;
	}
	
	sort(a, a+n);
	
	int ans = 0;
	for(auto x: st)
	{
		if(mp[x] > 1) continue;
		int ok1 = 1;
		for(int j=2;j*j<=x;j++)
		{
			if(x%j == 0)
			{
				if(binary_search(a, a+n, j))
				{
					ok1 = 0;
					break;
				}
				
				if(j*j != x)
				{
					if(binary_search(a, a+n, x/j))
					{
						ok1 = 0;
						break;
					}
				}
			}
		}
		
		ans += ok1;
	}
	
	cout << ans << "\n";
}









































































































































// Problem : D - Not Divisible
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define hell1 1000000007
#define hell2 1000000009
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ll long long
#define ld long double 
#define no_of_digits(n) floor(log10(n)) + 1
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define see(x) cout << #x << "=" << x << endl;
#define see2(x, y) cout << #x << "=" << x << "\t" << #y << "=" << y << endl;
#define see3(x, y, z) cout << #x << "=" << x << "\t" << #y << "=" << y << "\t" << #z << "=" << z << endl;
#define INF 1e9+5
#define LL_MAX 1e18+5

using namespace std;

const ld PI = acos((ld)-1);
 
ll modmult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
ll modmultbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=modmultbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;}
ll modadd(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
ll modsub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = modmult(r,n,p); n = modmult(n,n,p);} return r;}
ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}

int isPowerof2(ll x) { return (x && !(x & (x-1))); } 

ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; } 

bool isPerfectSquare(long double x) {long double sr = sqrt(x); return ((sr - floor(sr)) == 0); }
 
bool boundary(ll i,ll j,ll n, ll m){return (i>=0 && i<n && j>=0 &&  j<m);} //matrix boundary checking

ll ceil(const ll &a, const ll &b){return (a - 1)/b + 1;}
ll lcm(ll a, ll b){return a/__gcd(a, b)*b;}

 
string alpha="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

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

// cout << fixed for removing e notation
 
bool comp2(const pair<int, int>&a, const pair<int, int>&b)
{
    if(a.second < b.second)
        return true;
    else if(a.second == b.second)
    {
        if(a.fi > b.fi) return true;
        else return false;
    }
    else return false;
}
 
bool prime[10000005];
void SieveOfEratosthenes(int n) 
{
    memset(prime, true, sizeof(prime)); 
    prime[0] = prime[1] = 0;
    for (int p=2; p*p<=n; p++) 
    {
        if (prime[p] == true) 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
    }
}

int main()
{
	int n;
	cin >> n;
	
	int a[n];
	map<int, int>mp;
	set<int>st;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		st.insert(a[i]);
		mp[a[i]]++;
	}
	
	int ok = 0;
	for(auto x: mp)
	{
		if(x.se == 1)
		{
			ok = 1;
			break;
		}
	}
	
	if(!ok || mp[1])
	{
		cout << 0 << "\n";
		return 0;
	}
	
	sort(a, a+n);
	
	int ans = 0;
	for(auto x: st)
	{
		if(mp[x] > 1) continue;
		int ok1 = 1;
		for(int j=2;j*j<=x;j++)
		{
			if(x%j == 0)
			{
				if(binary_search(a, a+n, j))
				{
					ok1 = 0;
					break;
				}
				
				if(j*j != x)
				{
					if(binary_search(a, a+n, x/j))
					{
						ok1 = 0;
						break;
					}
				}
			}
		}
		
		ans += ok1;
	}
	
	cout << ans << "\n";
}






















































































































































Compiler output:
a.cc:321:10: error: redefinition of 'const long double PI'
  321 | const ld PI = acos((ld)-1);
      |          ^~
a.cc:34:10: note: 'const long double PI' previously defined here
   34 | const ld PI = acos((ld)-1);
      |          ^~
a.cc:323:4: error: redefinition of 'long long int modmult(long long int, long long int, long long int)'
  323 | ll modmult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
      |    ^~~~~~~
a.cc:36:4: note: 'long long int modmult(long long int, long long int, long long int)' previously defined here
   36 | ll modmult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
      |    ^~~~~~~
a.cc:324:4: error: redefinition of 'long long int modmultbig(long long int, long long int, long long int)'
  324 | ll modmultbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=modmultbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;}
      |    ^~~~~~~~~~
a.cc:37:4: note: 'long long int modmultbig(long long int, long long int, long long int)' previously defined here
   37 | ll modmultbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=modmultbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;}
      |    ^~~~~~~~~~
a.cc:325:4: error: redefinition of 'long long int modadd(long long int, long long int, long long int)'
  325 | ll modadd(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
      |    ^~~~~~
a.cc:38:4: note: 'long long int modadd(long long int, long long int, long long int)' previously defined here
   38 | ll modadd(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
      |    ^~~~~~
a.cc:326:4: error: redefinition of 'long long int modsub(long long int, long long int, long long int)'
  326 | ll modsub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
      |    ^~~~~~
a.cc:39:4: note: 'long long int modsub(long long int, long long int, long long int)' previously defined here
   39 | ll modsub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
      |    ^~~~~~
a.cc:327:4: error: redefinition of 'long long int fpow(long long int, long long int, long long int)'
  327 | ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = modmult(r,n,p); n = modmult(n,n,p);} return r;}
      |    ^~~~
a.cc:40:4: note: 'long long int fpow(long long int, long long int, long long int)' previously defined here
   40 | ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = modmult(r,n,p); n = modmult(n,n,p);} return r;}
      |    ^~~~
a.cc:328:4: error: redefinition of 'long long int inv(long long int, long long int)'
  328 | ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
      |    ^~~
a.cc:41:4: note: 'long long int inv(long long int, long long int)' previously defined here
   41 | ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
      |    ^~~
a.cc:329:4: error: redefinition of 'long long int inv_euclid(long long int, long long int)'
  329 | ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
      |    ^~~~~~~~~~
a.cc:42:4: note: 'long long int inv_euclid(long long int, long long int)' previously defined here
   42 | ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
      |    ^~~~~~~~~~
a.cc:331:5: error: redefinition of 'int isPowerof2(long long int)'
  331 | int isPowerof2(ll x) { return (x && !(x & (x-1))); }
      |     ^~~~~~~~~~
a.cc:44:5: note: 'int isPowerof2(long long int)' previously defined here
   44 | int isPowerof2(ll x) { return (x && !(x & (x-1))); }
      |     ^~~~~~~~~~
a.cc:333:4: error: redefinition of 'long long int log2(long long int)'
  333 | ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; }
      |    ^~~~
a.cc:46:4: note: 'long long int log2(long long int)' previously defined here
   46 | ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; }
      |    ^~~~
a.cc:335:6: error: redefinition of 'bool isPerfectSquare(long double)'
  335 | bool isPerfectSquare(long double x) {long double sr = sqrt(x); return ((sr - floor(sr)) == 0); }
      |      ^~~~~~~~~~~~~~~
a.cc:48:6: note: 'bool isPerfectSquare(long double)' previously defined here
   48 | bool isPerfectSquare(long double x) {long double sr = sqrt(x); return ((sr - floor(sr)) == 0); }
      |      ^~~~~~~~~~~~~~~
a.cc:337:6: error: redefinition of 'bool boundary(long long int, long long int, long long int, long long int)'
  337 | bool boundary(ll i,ll j,ll n, ll m){return (i>=0 && i<n && j>=0 &&  j<m);} //matrix boundary checking
      |      ^~~~~~~~
a.cc:50:6: note: 'bool boundary(long long int, long long int, long long int, long long int)' previously defined here
   50 | bool boundary(ll i,ll j,ll n, ll m){return (i>=0 && i<n && j>=0 &&  j<m);} //matrix boundary checking
      |      ^~~~~~~~
a.cc:339:4: error: redefinition of 'long long int ceil(const long long int&, const long long int&)'
  339 | ll ceil(const ll &a, const ll &b){return (a - 1)/b + 1;}
      |    ^~~~
a.cc:52:4: note: 'long long int ceil(const long long int&, const long long int&)' previously defined here
   52 | ll ceil(const ll &a, const ll &b){return (a - 1)/b + 1;}
      |    ^~~~
a.cc:340:4: error: redefinition of 'long long int lcm(long long int, long long int)'
  340 | ll lcm(ll a, ll b){return a/__gcd(a, b)*b;}
      |    ^~~
a.cc:53:4: note: 'long long int lcm(long long int, long long int)' previously defined here
   53 | ll lcm(ll a, ll b){return a/__gcd(a, b)*b;}
      |    ^~~
a.cc:343:8: error: redefinition of 'std::string alpha'
  343 | string alpha="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
      |        ^~~~~
a.cc:56:8: note: 'std::string alpha' previously declared here
   56 | string alpha="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
      |        ^~~~~
a.cc:345:5: error: redefinition of 'int dx [4]'
  345 | int dx[4] = {0, 0, -1, 1};
      |     ^~
a.cc:58:5: note: 'int dx [4]' previously defined here
   58 | int dx[4] = {0, 0, -1, 1};
      |     ^~
a.cc:346:5: error: redefinition of 'int dy [4]'
  346 | int dy[4] = {-1, 1, 0, 0};
      |     ^~
a.cc:59:5: note: 'int dy [4]' previously defined here
   59 | int dy[4] = {-1, 1, 0, 0};
      |     ^~
a.cc:350:6: error: redefinition of 'bool comp2(const std::pair<int, int>&, const std::pair<int, int>&)'
  350 | bool comp2(const pair<int, int>&a, const pair<int, int>&b)
      |      ^~~~~
a.cc:63:6: note: 'bool comp2(const std::pair<int, int>&, const std::pair<int, int>&)' previously defined here
   63 | bool comp2(const pair<int, int>&a, const pair<int, int>&b)
      |      ^~~~~
a.cc:362:6: error: redefinition of 'bool prime [10000005]'
  362 | bool prime[10000005];
      |      ^~~~~
a.cc:75:6: note: 'bool prime [10000005]' previously declared here
   75 | bool prime[10000005];
      |      ^~~~~
a.cc:363:6: error: redefinition of 'void SieveOfEratosthenes(int)'
  363 | void SieveOfEratosthenes(int n)
      |      ^~~~~~~~~~~~~~~~~~~
a.cc:76:6: note: 'void SieveOfEratosthenes(int)' previously defined here
   76 | void SieveOfEratosthenes(int n)
      |      ^~~~~~~~~~~~~~~~~~~
a.cc:375:5: error: redefinition of 'int main()'
  375 | int main()
      |     ^~~~
a.cc:88:5: note: 'int main()' previously defined here
   88 | int main()
      |     ^~~~