求最优解,需要还原现场
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
int a[N];
int res = N;
int len;
vector<int>g[N];
bool check(int u, int c)
{
for (int i = 0; i < g[c].size(); i++)
if (gcd(g[c][i], u) > 1)return false;
return true;
}
void dfs(int u)
{
if (u == n)
{
res = min(res, len);
return;
}
for (int i = 0; i < len; i++)
{
if (check(a[u], i))
{
g[i].push_back(a[u]);
dfs(u + 1);
g[i].pop_back();
}
}
g[len++].push_back(a[u]);
dfs(u + 1);
g[--len].pop_back();
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
dfs(0);
cout << res << endl;
return 0;
}