利用线性规划求解因子图中的最长简单路径

因子图是指将一个正整数n拆成若干个质因数的乘积，每个质因数作为一个节点，如果两个数a, b的乘积能被n整除，则在节点a和节点b之间连一条有向边。最长简单路径指的是从某个节点开始，不经过重复节点的情况下，到达另一个节点的最长路径。该问题可以用线性规划求解，具体步骤如下：

1. 将因子图转化为连通的强分支图，并将其表示为邻接矩阵的形式。
2. 定义一个变量x(i, j)表示从节点i到节点j的路径是否存在，若存在则x(i, j)=1，否则x(i, j)=0。
3. 定义问题的目标函数为Maximize（∑x(i, j)）。
4. 定义约束条件： a. x(i, j)+x(j, k)≤1，表示任意两个节点之间的路径不能重复经过。 b. x(j, i)-x(i, j)≤0，表示所有路径都必须是有向的，不能反悔。 c. ∑x(i, j)≤n-1，表示路径的长度不能超过n-1。
5. 使用线性规划求解器求解该问题，得到最长路径。

下面是用Python代码实现该算法的示例：

from scipy.optimize import linprog

# 将因子图转化为邻接矩阵
def build_adj_matrix(n):
    adj_matrix = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if (i + 2) * (j + 2) == n:
                adj_matrix[i][j] = 1
    return adj_matrix

# 利用线性规划求解最长路径
def longest_path(n):
    A_eq = []
    b_eq = []
    constraints = []
    c = []
    adj_matrix = build_adj_matrix(n)
    for i in range(n):
        for j in range(n):
            c.append(-adj_matrix[i][j])
    for i in range(n):
        for j in range(n):
            if i != j:
                row = [