Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
763 B
2
Indexable
Never
#include<iostream>

using namespace std;
int n;
int a[17];
int ans;
int vs[17];
bool checksnt(int m)
{
	int count =0;
	for(int i=1;i<=m;i++)
		if(m%i==0) count++;
	if(count==2) return true;
	else return false;
}
void backtrack(int k, int st)
{
	vs[st]=1;
	if(k==n){
		int m1=a[0]+a[st];
		if(checksnt(m1)) ans++;
	}
	int m;
	for(int i=1;i<n;i++){
		if(vs[i]==0){
			m=a[i]+a[st];
			if(checksnt(m)){
				vs[i]=1;
				backtrack(k+1,i);
				vs[i]=0;
			}
		}
	}
	return;
}
int main()
{
	//eopen("input.txt","r",stdin);
	int T; cin >> T;
	for(int tc= 1; tc<=T;tc++){
		cin >>n;
		for(int i=0;i<n;i++){
			cin >> a[i];
			vs[i]=0;
		}
		ans=0;
		backtrack(1,0);
		cout<<"Case "<<tc<<": "<<ans<<endl;

	}
	return 0;
}