分成互质组【dfs】_dfs给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

蒜头君给定 n 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
输入格式

第一行是一个正整数 n。1≤n≤10。

第二行是 n 个不大于 10000 的正整数。
输出格式

一个正整数，即最少需要的组数。

输出时每行末尾的多余空格，不影响答案正确性

样例输入
6
14 20 33 117 143 175

样例输出
3

题目链接：https://nanti.jisuanke.com/t/T1216

解题思路：每个组开设一个数组存放，新的整数进行：1.如果与某个组的成员不影响互质性，那么就存放进这个组。 2.如果不存在1的情况，那么就另开一个组单独存放此整数。

/*
对每个数进行遍历:
1.和已有组的成员不影响互质性，就放进去
2.如果有影响，不能放入任何一个已有组，就自成一组
*/
#include <iostream>
#include <vector>
using namespace std;
int n;
int digits[15];
int groupcount;
vector <int> groups[15];
int gys(int a,int b){
    if( b == 0 )   return a;
    return   gys(b,a%b);
}

void dfs(int index){  //现在正在处理第index个数（第index还没处理）
    if(index == n)   return ;
    int t=0;
    int flag2=0;
    for(int i=0;i<groupcount;i++) //遍历已有的每个组，判断互质
    {
        int flag1=0;
        for(int j=0;j<groups[i].size();j++)
        {
            if(digits[index] <= groups[i][j])
                t=gys(groups[i][j],digits[index]); 
            else
                t=gys(digits[index],groups[i][j]);
            if( t !=1 )
            {
                flag1=1;
                break;
            }       
        }
    if(flag1 == 0)
    {
        flag2=1;
        groups[i].push_back(digits[index]);
        break;
    }    
    }
    if( flag2 == 0) groups[groupcount++].push_back(digits[index]);
    dfs(index+1);
    return ;
}
int main(){
    cin >> n ;
    for(int i=0;i<n;i++)
    {
        cin >> digits[i];
    }
    dfs(0);
    cout << groupcount << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57