题解

注意到 $N=10^6$。普通的 $N\sqrt A_i$ 算法肯定会 T。思考怎么优化。
在 这题 中有个著名的卡常技巧：提前筛出所有的质数，然后枚举时遍历质数就行了。
因为 $\pi(n)\approx \frac{n}{\ln n}$，所以这样就可以把时间复杂度降到 $O(\frac{N\sqrt A_i}{\ln A_i})$。

如果还不放心，想着可能如果有极限数据（如 $N,A_i=10^6$），那么把数组去个重就行了，反正重复的对不同的质因子的贡献没有任何作用。

// O(n\sqrt n/ln n) 能过吗 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int a[1000005];
bool vis2[1000005];
bool vis[1000005];
vector <int> primes;
int n, ans;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(int i = 2; i <= 1000; i++){
		if(vis2[i]) continue;
		for(int j = i * 2; j <= 1000000; j += i){
			vis2[j] = 1;
		}
	}
	for(int i = 2; i <= 1000000; i++){
		if(!vis2[i]) primes.push_back(i);
	}
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	n = unique(a + 1, a + n + 1) - a - 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < primes.size() && primes[j] * primes[j] <= a[i]; j++){
			if(a[i] % primes[j] == 0){
				if(!vis[primes[j]]) vis[primes[j]] = 1, ans++;
				while(a[i] % primes[j] == 0) a[i] /= primes[j];
			}
		}
		if(a[i] != 1 && !vis[a[i]]) vis[a[i]] = 1, ans++;
	}
	cout << ans;
	
	return 0;
}

---

@BaiRX运用了神秘方法，使疑似 $O(N\sqrt N\log N)$ 的解法通过了，令人忍俊不禁。