How to find a sequence like this?

The problem is as follows.

You are given a natural number n (2 <= n <= 10⁹) and you have to build a sequence with its divisors (d₁, d₂, d₃ ...) so that for every pair of subsequent divisors one of these two rules is complied with. If d_i < d_i+1 then d_i+1%d_i must be 0 and d_i+1/d_i must be a prime number and the other way around If d_i > d_i+1 then d_i%d_i+1 must be 0 and d_i/d_i+1 must be a prime number.

Let me give you an example. n = 20 so {1, 2, 4, 20, 10, 5} can be an answer because

1 < 2 && 2%1 == 0 && 2/1 = 2 which is a prime number

2 < 4 && 4%2 == 0 && 4/2 = 2 which is a prime number

4 < 20 && 20%4 == 0 && 20/4 = 5 which is a prime number

20 > 10 && 20%10 == 0 && 20/10 = 2 which is a prime number

10 > 5 && 10%5 == 0 && 10/5 = 2 which is a prime number

#include <vector>
#include <bitset>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <iterator>

std::size_t constexpr sz_max{ 1500 };
std::vector<int> div_list, ans;
std::vector<std::vector<std::size_t>> edge_list;
std::bitset<sz_max> is_used;

bool is_prime(int src)noexcept {
    if (src == 2 || src == 3) {
        return true;
    }
    if (src <= 1 || (src & 1) == 0 || src % 3 == 0) {
        return false;
    }
    for (int div{ 5 }; div * div <= src; div += 6) {
        if (src % div == 0 || src % (div + 2) == 0) {
            return false;
        }
    }
    return true;
}

bool is_valid(int lhs, int rhs)noexcept {
    return (lhs < rhs&& rhs% lhs == 0 && is_prime(rhs / lhs)) ||
        (lhs > rhs && lhs % rhs == 0 && is_prime(lhs / rhs));
}

bool is_sorted(std::vector<int> const& src)noexcept {
    for (std::size_t i{ 0 }; i + 1 != src.size(); ++i) {
        if (!is_valid(src[i], src[i + 1])) {
            return false;
        }
    }
    return true;
}

void DFS(std::size_t i)noexcept {
    ans.emplace_back(div_list[i]);
    is_used.set(i, true);
    for (std::size_t curr : edge_list[i]) {
        if (!is_used.test(curr)) {
            DFS(curr);
        }
    }
    if (ans.size() != div_list.size()) {
        ans.pop_back();
        is_used.set(i, false);
    }
}

int main() {
    // 1
    int n;
    std::cin >> n;
    for (int div{ 1 }; div * div <= n; ++div) {
        if (n % div == 0) {
            div_list.emplace_back(div);
            if (div * div != n) {
                div_list.emplace_back(n / div);
            }
        }
    }
    // 2
    std::sort(div_list.begin(), div_list.end());
    // 3
    edge_list.resize(div_list.size());
    for (std::size_t i{ 0 }; i != div_list.size(); ++i) {
        for (std::size_t j{ 0 }; j != div_list.size(); ++j) {
            if (i != j && is_valid(div_list[i], div_list[j])) {
                edge_list[i].emplace_back(j);
            }
        }
    }
    // 4
    DFS(0);
    // 5
    assert(is_sorted(ans));
    // 6
    std::copy(ans.cbegin(), std::prev(ans.cend()),
        std::ostream_iterator<int>{ std::cout, " " });
    std::cout << ans.back() << '\n';
    return 0;
}

In //1 I find out the divisors of n and save them in div_list.

In //2 I sort the divisors in ascending order.

In //3 I build the edge list of a graph consisting of the divisors of n as vertices. edge_list[i] is a vector which keeps the indices of the viable neighbours of the divisor div_list[i].

In //4 I build the sequence ans using DFS algorithm which uses the bitset is_used to mark the visited vertices. In this block

    if (ans.size() != div_list.size()) {
        ans.pop_back();
        is_used.set(i, false);
    }

I'm implementing backtracking in case of running into dead end. The constant sz_max is high enough I think to cover the cases where n has too many divisors.

In //5 I double check the sequence ans.

In //6 I output ans.

The problem is that DFS tries every possible path until it finds the correct one. For some numbers the algorithm runs very fast (2162160, 1000000000) but for others it runs for ages (not because It is wrong but because of the recursive calls It has to make). For example 223092870, 555710400 and 707691600.

Question 1: Is is somehow possible to improve the algorithm ?

Question 2: If not and I have to select different strategy which one It has to be ?

This is indeed a search of Hamiltonian path in the lattice of divisors of n. We can prove that such a Hamiltonian path exists, because the lattice of divisors is a product of line graphs for each divisor (see, for example, this answer)

Therefore, you can use this proof to find a path as follows.

1. Find all prime divisors d_i of n, and their powers p_i.
2. Start with 1.
3. If you have constructed a path P using only prime divisors d_j, j<i, you can construct a path additionally using prime divisor d_i: P, d_i * P', d_i^2 * P, d_i^3 * P', ..., d_i^p_i * P. Here I denote by P' a reversed path P, and by k * P a path where each element is multiplied by k.
4. Repeat step 3 for all prime divisors.

To clarify meaning of step 3. Suppose that you have a path P = 1,2,4, and your next d_i = 5, p_i = 4. Then you get a path (1,2,4), (20,10,5), (25,50,100), (500,250,125). I enclosed each part of the new path in brackets, first part is simply P, second - 5 * P', third - 25 * P, fourth - 125 * P'.

This algorithm is linear in number of divisors.

Here is the main part of solution (I haven't written C++ in ages, excuse me for its style):

ans.emplace_back(1);
for (int i=0; i<prime_divs.size(); i++) {
    int d = prime_divs[i];
    int n = ans.size();
    int pos = n-1;
    for (int j=0; j<prime_pows[i]; j++) {
        for (int k=pos; k>=pos-n+1; k--) {
            ans.emplace_back(ans[k] * d);
        }
        pos += n;
    }
}

I tested it on your examples, and it outputs a list with all divisors in the required order.