题解

$N\le 10^6,A_i\le 10^6$ 注意到这个，朴素的 $O(nA_i)$ 方法肯定不能过。
下意识的想到筛法，于是就打了一个。
便可以优化成 $O(\frac{nA_i}{\ln n})$ 的算法，但这还不够。
注意到：对于一个数 $n$ 它最多只有一个大于 $\sqrt n$ 的质因子
于是，时间复杂度可以优化成 $O(\frac{n\sqrt A_i}{\ln n})$ 。
最多运行次数在 $1e6*997/6.907\approx 1.4e8$ ,加上判断（剪枝）可以勉强跑过。
$code:$

# include <bits/stdc++.h>
typedef unsigned long long ull;

#define getchar getchar_unlocked()
#define psbc push_back
#define v vector
#define for1 for(i = 0;i<n;i++)
#define be(x) x.begin(),x.end()
#define mkp make_pair

using  namespace  std ;
const int MX = 1e6;
int i,j,k;
int r(){
    int x = 0,f = 1;
    char c = getchar;
    while(c<'0'||c>'9'){if(c=='-') f = -1;c = getchar;}
    while(c>='0'&&c<='9') x = (x<<1)+(x<<3)+(c^(3<<4)),c = getchar;
    return x*f;
}
bool visited[MX+1],ct[MX];
int  main ( )
{
    int n = r(),ans = 0;
    v<int>arr(n);
    visited[0] = visited[1] = 1;
    for(i = 2;i<998;i++){
        if(!visited[i]){
            for(j = i*i;j<=MX;j += i){
                visited[j] = 1;
            }
        }
    }
    for1 arr[i] = r();
    for(auto i:arr){
        if(!visited[i]) ct[i] = 1;
        else{
            // cout<<i<<endl;
            for(j = 2;j<=ceil(sqrt(i));j++){
				if(i%j==0&&!visited[j]){
                    // cout<<j<<endl;
                    ct[j] = 1;
                    while(i%j==0){
                        i /= j;
                    }
                }
                if(i==1){
                    break;
                }
            }
        }
        if(i!=1) ct[i] = 1;
    }
    for(i = 2;i<1000000;i++){
        if(ct[i]){
            ans++;
            // cout<<i<<endl;
        }
    }
    cout<<ans;
    return  0;
}