How can I order divisors of N so that their quotients are prime numbers?

Question

I'm working on a problem where, given an integer N, I need to find all its divisors and print them in an order such that for any two consecutive divisors in the list, the following condition holds:

The larger divisor divided by the smaller divisor results in a prime number.

For example, for N = 12, one possible valid ordering of the divisors is:

1 2 4 12 6 3

In this sequence:

• 2/1=2 (prime)
• 4/2=2 (prime)
• 12/4=3 (prime)
• 12/6=2 (prime)
• 6/3=2 (prime)

If there are multiple valid solutions, any of them will suffice.

I’ve written a solution that finds all the divisors of N and sorts them, but I’m struggling to figure out how to order them based on this prime quotient condition. For instance, for N = 12, I can achieve the output 1 2 4 12 6 3, but I can't consistently generate such sequences for other values of N.

My Question:

How can I approach this problem and build the correct sequence of divisors for any integer N that satisfies the prime quotient condition? Any insights or suggestions would be appreciated!

Additional Context: I'm using C++ for the solution, and performance is a concern for larger values of N.

I’ve written a solution that finds all the divisors of N and sorts them, but I’m struggling to figure out how to order them based on this prime quotient condition. Below is a minimal example of my current code:

Input:

2
12
100

Output:

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

Find one prime factor and its exponent. For example for N=36, find 2^2. Divide that out so you have N=9 left. Solve that recursively, so you get for example the sequence 1 3 9. Now incorporate the 2^2 by going up and down, multiplying by 2 in between:

(1 3 9) (18 6 2) (4 12 36)

Python implementation:

def divs(n, i=2):
  if n == 1:
    return [1]
  while i * i <= n:
    e = 0
    while not n % i:
      n //= i
      e += 1
    if e:
      ds = divs(n, i+1)
      result = ds[:]
      while e:
        ds.reverse()
        ds = [d * i for d in ds]
        result += ds
        e -= 1
      return result
    i += 1
  return [1, n]

print(*divs(12))
print(*divs(36))

Output (Attempt This Online!):

1 3 6 2 4 12
1 3 9 18 6 2 4 12 36

More direct bottom-up way:

def divs(n):
  result = [1]
  i = 2
  while n > 1:
    if i * i > n:
      i = n
    ds = result
    while not n % i:
      n //= i
      ds = [d * i for d in reversed(ds)]
      result += ds
    i += 1
  return result

print(*divs(12))
print(*divs(36))

Output (Attempt This Online!):

1 2 4 12 6 3
1 2 4 12 6 3 9 18 36