答案:<pre class="brush:cpp;toolbar:false;">// 参考答案1:
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int n, cnt, ans = N, p[N];
vector<int> s[N];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int k, int x) {
for (int i = 0; i < s[k].size(); i++)
if (gcd(s[k][i], x) > 1)
return false;
return true;
}
void dfs(int u) {
if (u == n) {
ans = min(ans, cnt);
return;
}
for (int i = 0; i < cnt; i++)
if (check(i, p[u])) {
s[i].push_back(p[u]);
dfs(u + 1);
s[i].pop_back();
}
s[cnt++].push_back(p[u]);
dfs(u + 1);
s[--cnt].pop_back();
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i];
dfs(0);
cout << ans << endl;
return 0;
}</pre><p><span> </span><br/></p><pre class="brush:cpp;toolbar:false">// 参考答案2:
#include <iostream>
using namespace std;
const int N = 15;
int n;
int p[N];
int group[N][N];
bool used[N];
int ans = N;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int group[], int k, int x) {
for (int i = 0; i < k; i++)
if (gcd(p[group[i]], x) > 1)
return false;
return true;
}
void dfs(int g, int gc, int cnt, int start) {
if (g >= ans)
return;
if (cnt == n)
ans = g;
bool flag = false;
for (int i = start; i < n; i++)
if (!used[i] && check(group[g], gc, p[i])) {
used[i] = true;
group[g][gc] = i;
dfs(g, gc + 1, cnt + 1, i + 1);
used[i] = false;
flag = true;
}
if (!flag)
dfs(g + 1, 0, cnt, 0);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i];
dfs(1, 0, 0, 0);
cout << ans << endl;
return 0;
}</pre><p><br/><span></span></p>
这道题暂未补解析。