#include<bits/stdc++.h> using namespace std; int gcd(int a, int b) { if (b == 0)return a; else return gcd(b, a%b); } int flag[1000]; int getFather(int x) { if (flag[x] == -1)return x; else { int tmp = getFather(flag[x]); flag[x] = tmp; return tmp; } } int main() { int n; cin >> n; vector<int>sugar(n); vector<int>nums(n); for (int i = 0; i < n; i++) { cin >> sugar[i]; flag[i] = -1; nums[i] = 1; } for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { if (gcd(sugar[i], sugar[j]) > 1) { int a = getFather(i); int b = getFather(j); if (a != b) { flag[a] = b; nums[b] += nums[a]; } } } } int res = 0; for (int i = 0; i < n; i++) res = max(res, nums[i]); cout << res << endl; return 0; } 我用并查集做的，也是70%