---

Problem 881

---

Divisor Graph Width

For a positive integer $n$ create a graph using its divisors as vertices. An edge is drawn between two vertices $a<b$ if their quotient $b/a$ is prime. The graph can be arranged into levels where vertex $n$ is at level $0$ and vertices that are a distance $k$ from $n$ are on level $k$. Define $g(n)$ to be the maximum number of vertices in a single level.

The example above shows that $g(45)=2$. You are also given $g(5040)=12$.

Find the smallest number, $n$, such that $g(n)\ge {10}^4$.

---

约数图宽度

对于正整数$n$，以其约数为顶点构造图。若两个顶点$a<b$的商$b/a$是质数，则连接这两个顶点。该图可以分成多层，其中顶点$n$在第$0$层，而距离$n$的距离为$k$的顶点则位于第$k$层。记$g(n)$为该图中任意一层的顶点数的最大值。

如上所示可知$g(45)=2$。已知$g(5040)=12$。

求最小的、满足$g(n)\ge {10}^4$的$n$。

---