881. Divisor Graph Width

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

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

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

881. 因子图的宽度

我们可以用一个正整数 $n$$n$，利用如下规则构造其因子图：将 $n$$n$ 的所有因子作为该图的所有节点；若两个节点 $a,b(a<b)$$a, b (a < b)$ 满足 $b/a$$b/a$ 是质数，则在 $a,b$$a, b$ 之间连一条无向边。这图可以被分为若干层，其中节点 $n$$n$ 在第 $0$$0$ 层，所有与节点 $n$$n$ 的最短路为 $k$$k$ 的节点均在第 $k$$k$ 层。记 $g(n)$$g(n)$ 为 $n$$n$ 的因子图中，某层中含有节点数的最大值。

上图表明 $g(45)=2$$g(45) = 2$，又已知：$g(5040)=12$$g(5040) = 12$。

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

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。