质数相关

描述

两个数a和 b (a<b)被称为质数相关，是指a × p = b，这里p是一个质数。一个集合S被称为质数相关，是指S中存在两个质数相关的数，否则称S为质数无关。如{2, 8, 17}质数无关，但{2, 8, 16}, {3, 6}质数相关。现在给定一个集合S，问S的所有质数无关子集中，最大的子集的大小。

输入

第一行为一个数T，为数据组数。之后每组数据包含两行。

第一行为N，为集合S的大小。第二行为N个整数，表示集合内的数。

输出

对于每组数据输出一行，形如"Case #X: Y"。X为数据编号，从1开始，Y为最大的子集的大小。

数据范围

1 ≤ T ≤ 20

集合S内的数两两不同且范围在1到500000之间。

小数据

1 ≤ N ≤ 15

大数据

1 ≤ N ≤ 1000

样例输入

352 4 8 16 3252 3 4 6 931 2 3

样例输出

Case #1: 3Case #2: 3Case #3: 2 分析： 该题实际上是求集合子集的问题的延伸。

#include
     
      #include
      
       #include
       
        #include 
        
         using namespace std;bool isPrime(int p){	if(p<4)		return true;	int root = sqrt((double)p);	for(int i=2; i<=root; i++)	{		if(p%root==0)			return false;	}	return true;}void getMaxSubSetNum(int* a, int k, int n, vector
         
           sub, vector
          
           & maxSub){ if(k>=n) { if(sub.size()>maxSub.size()) maxSub = sub; return; } bool sign = false; for(int i=0; i
           

res; vector

sub, maxSub; int a[1000]; cin>>T; while(T--) { maxSub.clear(); cin>>N; for(int i=0; i

>a[i]; } sort(a, a+N); getMaxSubSetNum(a, 0, N, sub, maxSub); res.push_back(maxSub.size()); } for(int i=0; i