C++ :

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int a[N],group[N][N];
bool st[N];
int ans=N;
int n;
int gcd(int a,int b) //最大公约数
{
	if(b==0) return a;
	return gcd(b,a%b);
}
bool check(int g[],int gid,int i) //判断第u组的gid个元素和a[i]有没有冲突
{
	for(int j=0;j<gid;j++)
	{
		if(gcd(a[g[j]],a[i])>1)
		{
			return false; //有冲突
		}
	}
	return true; //没有冲突
}
void dfs(int u,int gid,int cnt,int s) 
//第u组，第u组移动gid个元素，当前一共搜索了cnt个元素，当前组从s开始搜索
{
	if(u>=ans) return ; //优化
	if(cnt==n) //一共找到了n个
	{
		ans=u;
		return ;
	}
	bool flag=true;
	for(int i=s;i<n;i++) //枚举以后的每个元素
	{
		if(!st[i]&&check(group[u],gid,i))
		{
			st[i]=1;
			group[u][gid]=i;
			dfs(u,gid+1,cnt+1,i+1);
			st[i]=0;
			flag=false;
		}
	}
	if(flag) //还有元素且没有办法加到其它组里
	{
		dfs(u+1,0,cnt,0);
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	dfs(1,0,0,0);
	cout<<ans<<endl;
	return 0;
}