HihoCoder 1158 : 质数相关 （最大独立集）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1010;
const int maxm=500010;
int link[maxn],used[maxn],a[maxn];
vector<int>G[maxn];
bool p[maxm];
void prime()
{
    for(int i=2;i<=500000;i++){
        if(!p[i]) {
               for(int j=i+i;j<=500000;j+=i)
                    p[j]=true;
        }
    }
}
bool find(int u)
{
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(used[v]) continue;
        used[v]=1;
        if(!link[v]||find(link[v])){
            link[v]=u;
            return true;
        }
    }
    return false;
}
int main()
{
    int i,j,n,T,ans=0,Case=0;
    prime();
    scanf("%d",&T);
    while(T--){
        ans=0;
        memset(link,0,sizeof(link));
        scanf("%d",&n);
        for(i=1;i<=n;i++) G[i].clear();
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(i=1;i<=n;i++)
         for(j=i+1;j<=n;j++){
                int tmp=a[j]/a[i];
                if(tmp*a[i]==a[j]&&!p[tmp]){
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
         }
        for(i=1;i<=n;i++){
             memset(used,0,sizeof(used));
             if(find(i)) ans++;
        }
        printf("Case #%d: ",++Case);
        printf("%d
",n-ans/2);
    }
    return 0;
}