如何对 N 的约数进行排序，使其商为素数？

Question

我正在解决一个问题，给定一个整数N，我需要找到它的所有除数并按顺序打印它们，以便对于列表中的任何两个连续除数，满足以下条件：

较大的除数除以较小的除数会得到素数。

例如，对于 N = 12，除数的一种可能的有效排序是：

1 2 4 12 6 3

按此顺序：

• 2/1=2（素数）
• 4/2=2（素数）
• 12/4=3（素数）
• 12/6=2（素数）
• 6/3=2（质数）

如果有多个有效的解决方案，其中任何一个就足够了。

我已经编写了一个解决方案，可以找到 N 的所有约数并对它们进行排序，但我正在努力弄清楚如何根据这个素商条件对它们进行排序。例如，对于 N = 12，我可以实现输出

1 2 4 12 6 3

，但我无法一致地为 N 的其他值生成这样的序列。

我的问题：

如何解决这个问题并为满足素商条件的任何整数N构建正确的除数序列？任何见解或建议将不胜感激！

其他上下文：我使用 C++ 来解决该问题，性能是较大的 N 值所关心的问题。

我已经编写了一个解决方案，可以找到 N 的所有约数并对它们进行排序，但我正在努力弄清楚如何根据这个素商条件对它们进行排序。以下是我当前代码的最小示例：

输入：

2
12
100

输出：

1 2 4 12 6 3
1 2 4 20 10 5 25 50 100

#include<bits/stdc++.h>
using namespace std;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MOD 1000000007
#define endl "\n"

const int N = 1e3 + 7;

int32_t main() {
    optimize();
    
    int t; 
    cin >> t; // Read number of test cases
    while (t--) {
        vector<int> v, ans;
        int n; 
        cin >> n; // Read the integer N
        
        // Find all divisors of n
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                if (j == n) {
                    v.push_back(i);
                }
            }
        }

        // Attempt to build the sequence of divisors (incomplete logic)
        // You need to implement the logic here to order the divisors based on the prime quotient condition

        // Print the divisors for now
        for (int val : v) {
            cout << val << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Answer 1

创建图表（数据结构）

将所有除数设置为图节点

用素数比率在节点之间制作边
（使用初始数的质因数分解会更容易 - 只需同时生成除数和边）

找到通过所有节点的欧拉路径