暴力题解

笑点解析：赛时没看数据范围写的然后 AC 顺便首 A

思路

$O(\sqrt{n})$ 直接暴力分解质因数（$n^{\frac{1}{4}}$ 的 PR 懒得调了），然后使用 set 维护即可。
时间复杂度为 $O(\sum_{i=1}^n\sqrt{a_i}\log{\sum_{i=1}^n\sqrt{a_i}})$（我补刀啊瞎猜的）

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,i;
set<int> s; 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a;
		for(int j=2;j*j<=a;j++)
		{
			if(a%j==0)
			{
				s.insert(j);
				while(a%j==0)a/=j;
			}
		}
		if(a>1)s.insert(a);
	}
	cout<<s.size();
	return 0;
}