题意：n个点，每个点有一个点权。两个点之间有边相连的充要条件是它们的点权不互素，问你这张图的连通块数。
从小到大枚举每个素数，然后枚举每个素数的倍数，只要这个素数的某个倍数存在，就用并查集在这些倍数之间都连上边。然后输出最后的集合数量即可。
注意，点权为1的点都会自成一个连通块。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T,a[1000006],fa[1000006],f[1000006],p[1000006],ans,n,t,notPrime[1000006],prime[1000006],num;
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
void un(int x,int y)
{
int Y=get(y);int X=get(x);
if(X!=Y)
{
fa[X]=Y;
}
}
char ch;
int temp;
int read()
{
while(ch=getchar(),ch<'0'||ch>'9');
temp=ch-'0';
while(ch=getchar(),ch<='9'&&ch>='0')
temp=temp*10+ch-'0';
return temp;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
for(int i=2;i<=1000000;++i)
{
if(!notPrime[i])
{
prime[++num]=i;
}
for(int j=1;j<=num&&prime[j]*i<=1000000;++j)
{
notPrime[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
scanf("%d",&T);
int maxi=1000000;
for(int tt=1;tt<=T;++tt)
{
n=read();
for(int i=1;i<=maxi;++i)
{
fa[i]=i;
f[i]=0;
a[i]=0;
}
maxi=0;
ans=0;
for(int i=1;i<=n;++i)
{
t=read();
if(t==1) ans++;
maxi=max(maxi,t);
a[t]=1;
}
for(int i=1;i<=num;++i)
{
int now=prime[i];
int tail=0;
for(int j=1;now*j<=maxi;++j)
{
if(a[now*j])
p[++tail]=now*j;
}
for(int j=1;j<tail;++j)
{
un(p[j],p[j+1]);
}
}
for(int i=2;i<=maxi;++i)
if(a[i])
{
if(!f[get(i)]) ans++;
f[get(i)]=1;
}
printf("Case %d: %d\n",tt,ans);
} }