用埃氏筛O(nlog(logn))求得1~5e6每个数的质因数个数,用并查集来维护连通块的大小，合并时判断两个数的最大公约数是否含有两个以上的质因数，如果是则合并，最后遍历所有位置，输出最大连通块大小即可。维护连通块不难，建图用dfs搜索也可以实现。困难的是想到可以用gcd的约数个数判断是否优雅，和在nlogn时间内处理出每个数的质因数个数。（我最开始是对每个数分解质因数，结果是超时了），考验的是对gcd和素数筛的理解。 
#include <iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
const int N = 1e6 + 10;
int cnt[5000010];
bool st[5000010];
int a[N], p[N], sz[N];
int find(int x) {
    if (x != p[x])p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y) {
    x = find(x);y = find(y);
    if (x != y) {
        p[y] = p[x];
        sz[x] += sz[y];
    }
}
void init() {
    int N = 5e6;
    for (int i = 2;i <= N;i++) {
        if (st[i])continue;
        for (int j = i+i;j <= N;j += i) {
            cnt[j]++;
            st[j] = true;
        }
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    init();
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        p[i] = i, sz[i] = 1;
    }
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    for (int i = 1;i < n;i++) {
        int l, r;
        cin >> l >> r;
        int gd = __gcd(a[l], a[r]);
        if (cnt[gd] >= 2)merge(l, r);
    }
    int res = 0;
    for (int i = 1;i <= n;i++) {
        if (p[i] == i)res = max(res, sz[i]);
    }
    cout << res << endl;
    return 0;
}