#include <stdio.h>
#include <stdlib.h>
 
int find(int n, int *pathMin)
{
  if (n == 0) return 0; // start backtracking with path length 0
  pathMin[0] = n;
  if (n == 1) return 1; // trivial result
  int lenMin = n;
  int *path = malloc(n * sizeof n);
  for (int a = n; a > 1; --a) {
    int b = n / a;
    if (a < b) break; // symmetric solutions which are already tested
    if (a * b != n) continue;
    // sufficient pair (a, b) found
    int len = find(a - 1, path);
    // override lenMin if a shorter path was found
    if (lenMin > len) {
      lenMin = len;
      // store current shortest path (it could be final result)
      memcpy(pathMin + 1, path, len * sizeof *path);
    }
  }
  free(path);
  return lenMin + 1;
}
 
void printShortestPath(int n)
{
  if (n <= 0) {
    fprintf(stderr, "n should be > 0!\n");
    return;
  }
  int *path = malloc(n * sizeof n);
  int len = find(n, path);
  printf("Length of shortest path to %d: %d\n", n, len);
  printf("Path:");
  for (int i = 0; i < len; ++i) printf(" %d", path[i]);
  putchar('\n');
  free(path);
}
 
int main(void)
{
  // a brute-force test for a range of numbers:
  for (int n = 1; n <= 20; ++n) {
    printShortestPath(n);
  }
  // done
  return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCmludCBmaW5kKGludCBuLCBpbnQgKnBhdGhNaW4pCnsKICBpZiAobiA9PSAwKSByZXR1cm4gMDsgLy8gc3RhcnQgYmFja3RyYWNraW5nIHdpdGggcGF0aCBsZW5ndGggMAogIHBhdGhNaW5bMF0gPSBuOwogIGlmIChuID09IDEpIHJldHVybiAxOyAvLyB0cml2aWFsIHJlc3VsdAogIGludCBsZW5NaW4gPSBuOwogIGludCAqcGF0aCA9IG1hbGxvYyhuICogc2l6ZW9mIG4pOwogIGZvciAoaW50IGEgPSBuOyBhID4gMTsgLS1hKSB7CiAgICBpbnQgYiA9IG4gLyBhOwogICAgaWYgKGEgPCBiKSBicmVhazsgLy8gc3ltbWV0cmljIHNvbHV0aW9ucyB3aGljaCBhcmUgYWxyZWFkeSB0ZXN0ZWQKICAgIGlmIChhICogYiAhPSBuKSBjb250aW51ZTsKICAgIC8vIHN1ZmZpY2llbnQgcGFpciAoYSwgYikgZm91bmQKICAgIGludCBsZW4gPSBmaW5kKGEgLSAxLCBwYXRoKTsKICAgIC8vIG92ZXJyaWRlIGxlbk1pbiBpZiBhIHNob3J0ZXIgcGF0aCB3YXMgZm91bmQKICAgIGlmIChsZW5NaW4gPiBsZW4pIHsKICAgICAgbGVuTWluID0gbGVuOwogICAgICAvLyBzdG9yZSBjdXJyZW50IHNob3J0ZXN0IHBhdGggKGl0IGNvdWxkIGJlIGZpbmFsIHJlc3VsdCkKICAgICAgbWVtY3B5KHBhdGhNaW4gKyAxLCBwYXRoLCBsZW4gKiBzaXplb2YgKnBhdGgpOwogICAgfQogIH0KICBmcmVlKHBhdGgpOwogIHJldHVybiBsZW5NaW4gKyAxOwp9Cgp2b2lkIHByaW50U2hvcnRlc3RQYXRoKGludCBuKQp7CiAgaWYgKG4gPD0gMCkgewogICAgZnByaW50ZihzdGRlcnIsICJuIHNob3VsZCBiZSA+IDAhXG4iKTsKICAgIHJldHVybjsKICB9CiAgaW50ICpwYXRoID0gbWFsbG9jKG4gKiBzaXplb2Ygbik7CiAgaW50IGxlbiA9IGZpbmQobiwgcGF0aCk7CiAgcHJpbnRmKCJMZW5ndGggb2Ygc2hvcnRlc3QgcGF0aCB0byAlZDogJWRcbiIsIG4sIGxlbik7CiAgcHJpbnRmKCJQYXRoOiIpOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbGVuOyArK2kpIHByaW50ZigiICVkIiwgcGF0aFtpXSk7CiAgcHV0Y2hhcignXG4nKTsKICBmcmVlKHBhdGgpOwp9CgppbnQgbWFpbih2b2lkKQp7CiAgLy8gYSBicnV0ZS1mb3JjZSB0ZXN0IGZvciBhIHJhbmdlIG9mIG51bWJlcnM6CiAgZm9yIChpbnQgbiA9IDE7IG4gPD0gMjA7ICsrbikgewogICAgcHJpbnRTaG9ydGVzdFBhdGgobik7CiAgfQogIC8vIGRvbmUKICByZXR1cm4gMDsKfQo=