【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
【输入】
第一行是一个正整数n。1 ≤ n ≤ 10。
第二行是n个不大于10000的正整数。
【输出】
一个正整数，即最少需要的组数。
【输入样例】
6 14 20 33 117 143 175
【输出样例】
3
// Created on 2020/2/6
/*#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <string>*/
#include <bits/stdc++.h>
#define A 500+5
using namespace std;
//int i,j,k;
const int maxn=INT_MAX;
const int idata=20+5;
long long aim[idata];
bool judge[idata];
long long temp[idata];
int cnt=0;
char ch;
//int sum;
int t;
inline int gcd(long long a,long long b)//greatest common divisor
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
int cnt=1;
register int i,j;
cin>>t;
for(i=1;i<=t;i++)
{
cin>>aim[i];
}
memset(temp,1,sizeof(temp));
sort(aim+1,aim+1+t);//避免求公约数时再判断大小
temp[1]=aim[1];
for(i=2;i<=t;i++)
{
for(j=1;j<=cnt;j++)//每次筛选一个aim中的元素
{
if(gcd(aim[i],temp[j])==1)
{
temp[j]*=aim[i];
break;
}
}
if(j-1==cnt)//没有放入temp中（break 没有执行）
temp[++cnt]=aim[i];
}
cout<<cnt<<endl;
return 0;
}