如何对整数N的除数排序，使相邻两数的商为质数？

核心思路 #

要生成符合要求的序列，本质是构建除数的哈密顿路径——每个相邻除数的商为质数（大值除以小值）。这类序列可以通过以下步骤实现：

1. 高效获取所有除数 #

替换原O(n)的除数查找逻辑，改用O(√n)的方法，适合处理大N：

• 遍历1到√N，若i是N的因数，则同时加入i和N/i到除数列表，最后去重排序。

2. 质数判断优化 #

对于大数的质数判断，使用米勒-拉宾素性测试（比试除法高效得多），确保判断大质数时的性能。

3. 构建邻接表与DFS找路径 #

将每个除数视为图的节点，若两个除数的商为质数，则建立双向边。从1出发（1是所有N的除数，且必然是序列起点之一），用DFS遍历所有节点，找到包含所有除数的路径。

4. 更高效的递归构建法（可选） #

利用N的质因数分解特性，递归生成序列：

• 若N = p^k * M（p为质数，M与p互质），先生成M的合法序列，再对序列中每个元素x，依次生成xp、xp²…xp^{k，同时处理回溯分支（如从x*p}k除以p得到xp^(k-1)等），这种方法无需构建图，性能更优。

完整C++实现代码 #

#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 endl "\n"

// 米勒-拉宾素性测试，判断n是否为质数
bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;
    // 分解n-1为d*2^s
    int d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    // 测试底数集合，覆盖64位整数的所有情况
    vector<int> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (int a : bases) {
        if (a >= n) continue;
        int x = 1;
        // 快速幂计算a^d mod n
        int temp = d;
        int base = a;
        while (temp > 0) {
            if (temp % 2 == 1) {
                x = (__int128)x * base % n;
            }
            base = (__int128)base * base % n;
            temp /= 2;
        }
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int j = 1; j < s; j++) {
            x = (__int128)x * x % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

// 获取N的所有除数，排序后返回
vector<int> get_divisors(int n) {
    vector<int> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}

// DFS寻找哈密顿路径
bool dfs(int current, vector<bool>& visited, vector<int>& path, const vector<vector<int>>& adj, int total_nodes) {
    visited[current] = true;
    path.push_back(current);
    if (path.size() == total_nodes) {
        return true;
    }
    for (int neighbor : adj[current]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, visited, path, adj, total_nodes)) {
                return true;
            }
        }
    }
    // 回溯
    visited[current] = false;
    path.pop_back();
    return false;
}

int32_t main() {
    optimize();
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> divisors = get_divisors(n);
        int m = divisors.size();
        // 建立除数到索引的映射
        unordered_map<int, int> idx_map;
        for (int i = 0; i < m; i++) {
            idx_map[divisors[i]] = i;
        }
        // 构建邻接表
        vector<vector<int>> adj(m);
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                int a = divisors[i];
                int b = divisors[j];
                if (max(a, b) % min(a, b) != 0) continue;
                int q = max(a, b) / min(a, b);
                if (is_prime(q)) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        // 从1开始查找路径
        vector<bool> visited(m, false);
        vector<int> path;
        int start_idx = idx_map[1];
        dfs(start_idx, visited, path, adj, m);
        // 输出结果
        for (int idx : path) {
            cout << divisors[idx] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

代码说明 #

1. 米勒-拉宾素性测试：支持判断64位整数是否为质数，比试除法快几个数量级，适合大N的场景。
2. 除数获取：O(√n)时间复杂度，高效生成所有除数并排序。
3. 邻接表构建：遍历所有除数对，判断是否满足商为质数的条件，建立双向边。
4. DFS路径查找：从1出发，回溯寻找包含所有除数的路径，找到即返回（保证效率）。

性能优化点 #

• 对于超大N（如1e18），除数数量最多约1000个（取决于质因数分解的指数），DFS的时间完全可控。
• 若想进一步优化，可替换DFS为基于质因数分解的递归生成法，避免构建图的开销。

内容的提问来源于stack exchange，提问作者Nahin Ahmed