题目要点

1. 题目要求对于数$x$，它的约数和$y$小于它本身才就可以连边。我们可以利用这个性质把这道题目转化为1072（求树中最长路径）：一个数$y$可以作为多个数$[x_1,x_2,x_3,…]$的约数和，且满足上面的性质。因此我们可以把题目给定的$n$个数转化为一棵树，以 1 作为根节点。
2. 同时，这个题目中的可以不用邻接表来表示图，因为一个节点的根节点就是他的约数和，直接访问数组即可。
3. 最后，需要提前处理好$1-n$各个数字的约数和。

算法1

(DP) $O(n)$

从叶子节点开始处理，在处理到（满足条件的）约数和$y$时，找到它的所有子节点，记录子节点路径的最大(m1)和次大值(m2)，即可构成路径。

"""
AcWing 1075. 数字转换
"""
N = 50010
m1, m2 = [0] * N, [0] * N
count = [1] * N # 约数和


def solution():
    n = int(input())

    # 约数和处理
    for i in range(2, n // 2 + 1):
        for j in range(2 * i, n + 1, i):
            count[j] += i

    # DP
    for i in range(n, 1, -1):
        if i > count[i]:
            if m1[i] + 1 > m1[count[i]]:
                m2[count[i]] = m1[count[i]]
                m1[count[i]] = m1[i] + 1
            elif m1[i] + 1 > m2[count[i]]:
                m2[count[i]] = m1[i] + 1

    res = 0
    for i in range(1, n + 1):
        res = max(res, (m1[i] + m2[i]))

    print(res)


if __name__ == '__main__':
    solution()