题意

对于数组$a$中的每个元素 $a_i$,判断该 $a_i$的所有因子是否都存在在数组中。

对于本题$1 \le n \le 10^6$且 $1\le a_i \le 10^6$,暴力判断时间复杂度为$\sqrt a_i*n$,显然超时.

因此可以使用类似于素数筛的方法来筛出未出现数字的倍数，来判断$a_i$是否被标记 时间复杂度为 $n loglogn$

注意去重! 一个数可以出现两次。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000005];
ll b[1000005];
ll c[1000005];
int main()
{
	 ll n;
	 scanf("%lld",&n);
	 ll mx=0;
	 for(ll i=1;i<=n;i++)
	 {
		scanf("%lld",&a[i]);
		 b[a[i]]=1;//标记每个出现的数
		mx=max(a[i],mx);//找出最大的数max
	 }
	 for(ll i=1;i<=mx;i++)//遍历1-mx
     {
		if(b[i]==0)//如果该数没有出现
		{
			for(ll j=i;j<=mx;j+=i)//筛法，筛出所有倍数
			{
				c[j]=1;
			}
		}
	 }
	 ll ans=0;
	 for(ll i=1;i<=1e6;i++)//这种遍历可以免去去重
	 {
        if(c[i]==0&&b[i]==1)//如果该数出现并且没有被筛到，说明他的因子全在数组中，对答案贡献+1
		  ans++;
	 }
	 printf("%lld\n",ans);
}