human
I found an interesting problem on https://codeforces.com/problemset/problem/1101/D:
You are given a tree consisting of $n$ vertices. A number is written on each vertex.
the number on vertex $i$ is equal to $a_i$.

Let's denote the function $g(x, y)$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $x$ to vertex $y$ (including these two vertices). Also let's denote $dist(x, y)$ as the number of vertices on the simple path between vertices $x$ and $y$, including the endpoints. $dist(x, x) = 1$ for every vertex $x$.

Your task is calculate the maximum value of $dist(x, y)$ among such pairs of vertices that $g(x, y) > 1$.

-----Input-----

The first line contains one integer $n$ — the number of vertices $(1 \le n \le 2 \cdot 10^5)$.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le 2 \cdot 10^5)$ — the numbers written on vertices.

Then $n - 1$ lines follow, each containing two integers $x$ and $y$ $(1 \le x, y \le n, x \ne y)$ denoting an edge connecting vertex $x$ with vertex $y$. It is guaranteed that these edges form a tree.

-----Output-----

If there is no pair of vertices $x, y$ such that $g(x, y) > 1$, print $0$. Otherwise print the maximum value of $dist(x, y)$ among such pairs.

-----Examples-----
Input
3
2 3 4
1 2
2 3

Output
1

Input
3
2 3 4
1 3
2 3

Output
2

Input
3
1 1 1
1 2
2 3

Output
0

I tried it in Python, but could not do it. Can you solve it?
assistant
#Here is Python code to print $0$.

import math
import sys

def get_primes(n):
    result = set()
    while n % 2 == 0:
        result.add(2)
        n = n / 2

    for i in range(3, int(math.sqrt(n)) + 1, 2):

        while n % i == 0:
            result.add(i)
            n = n / i

    if n > 2:
        result.add(n)
    return list(result)


def calc(w, t, n):
    stack = []
    stack.append((t[0], dict([(p, [0]) for p in get_primes(w[0])])))
    max_length = 0
    visited = [False] * n
    visited[0] = True
    while stack:
        if stack[-1][0]:
            nxt = stack[-1][0][-1]
            stack[-1][0].pop()
            if visited[nxt]:
                continue
            else:
                visited[nxt] = True
            stack.append((t[nxt], dict([(p, [0]) for p in get_primes(w[nxt])])))
        else:
            last = stack[-1][1]
            stack.pop()
            if last:
                max_length = max(max_length, 1 + max([sum(v) for _, v in list(last.items())]))
            if stack:
                for k, v in list(last.items()):
                    if k in list(stack[-1][1].keys()):
                        stack[-1][1][k].append(max(v) + 1)
                        stack[-1][1][k].sort(reverse=True)
                        if len(stack[-1][1][k]) > 2:
                            del stack[-1][1][k][-1]
    return max_length

# def __starting_point():
#     print(primeFactors(100))

def __starting_point():
    n = int(input())
    weights = list(map(int, input().split()))
    lines = sys.stdin.readlines()
    tree = [[] for _ in range(n)]
    for line in lines:
        x, y = list(map(int, line.split()))
        tree[x - 1].append(y - 1)
        tree[y - 1].append(x - 1)

    print(calc(weights, tree, n))

__starting_point()