n = int(input())
def find_res(N):
    res = []
    def dfs(N,start,path):
        if N ==1:
            res.append(path.copy())
        for i in range(start,N+1):
            if N %i==0:
                path.append(i)
                dfs(N//i,i,path)
                path.pop()
    dfs(N,2,[])
    return res

res = find_res(n)
for line in res:
    print(str(n)+'='+'*'.join(map(str,line))

def factorize(N):
    result = []
    
    # 递归回溯函数
    def dfs(n, start, current):
        if n == 1:  # 如果n被分解到1，说明找到一种分解方式
            if len(current) > 1:  # 忽略只有一个元素的分解（即N本身）
                result.append(list(current))
            return
        
        # 从start开始，寻找可行的因子
        for i in range(start, n + 1):
            if n % i == 0:  # i 是 n 的因子
                current.append(i)  # 将因子加入当前分解方案
                dfs(n // i, i, current)  # 继续分解 n // i
                current.pop()  # 回溯，移除因子

    dfs(N, 2, [])
    
    return result

# 输入N
N = int(input())

# 获取所有分解方案
decompositions = factorize(N)

# 按字典序输出每个分解方案
for decomposition in decompositions:
    print(f"{N}=" + "*".join(map(str, decomposition)))

# 输出N本身的分解
print(f"{N}={N}")

看不懂递归，用老师的回溯改的

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> res;
vector<int>  t;

void dfs(int n,int start) {
    if (n == 1) {
        res.push_back(t);
        return ;
    }
    
    for (int i = start; i <= n; i++) {
        if (n % i == 0) {
           t.push_back(i);
           dfs(n/i,i);
           t.pop_back();
        }
    }
}

int main() {
    int n;
    cin >> n;
    dfs(n,2);

    for (auto t:res)
    {
        cout<<n<<"=";
        for (int  i = 0; i < t.size(); i++)
        {
           cout<<t[i];
           if (i!=t.size()-1)
           {
            cout<<"*";
           }
           
        }
        cout<<endl; 
    }
    
    return 0;
}

package realpbms.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * 回溯，暴力搜索答案
 * 又称dfs，递归选择
 * 这个题要求字典序，则要求优先从小往大搜索，并且后面的必须比前面的大，形成一个合法序列
 * 为了有它本身作为结果，要求从2或者当前最大数开始，搜到自己本身
 */
public class P1523 {
    static LinkedList<Integer> trace = new LinkedList<>();
    static List<List<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        backtrack(n);
        print(n);


    }

    private static void backtrack(int cur) {
        if (cur == 1) {
            res.add(new ArrayList<>(trace));
            return;
        }

        for (int i = trace.isEmpty() ? 2 : trace.getLast(); i <= cur; i++) {
            if (cur % i == 0) {
                trace.add(i);
                backtrack(cur / i);
                trace.removeLast();
            }
        }


    }

    private static void print(int n) {
        for (List<Integer> list : res) {
            System.out.print(n+"=");
            for (int i = 0; i < list.size(); i++) {
                if (i != list.size() - 1) {
                    System.out.print(list.get(i) + "*");
                } else {
                    System.out.print(list.get(i));
                }
            }
            System.out.println();
        }
    }
}

题面描述:

给定一个整数 $N$ (满足 $1 < N \leq 256$)，我们需要输出所有符合条件的分解形式 $N = a_1 * a_2 * a_3....a_x$，其中 $1 < a_i \leq a_j$ (当 $i \leq j$ 时)，并按照字典序排列。例如，输入 $24$ 时，输出应为所有可能的分解，如 $24=2*2*2*3$、$24=2*2*6$ 等，直到 $24=24$。对于输入仅为一个整数 $N$，程序需将其所有分解方式逐行输出。

思路:递归+质因分解

实现思路

1. 递归分解：

   • 使用递归函数 fac(int n, int p) 来进行质因分解，其中 $n$ 是当前待分解的数，$p$ 是当前分解时的最小因子。
   • 当 $n$ 为 1 时，返回一个包含空向量的结果，表示一种有效的分解。

2. 分解过程：

   • 从最小因子 $p$ 开始遍历所有可能的因子 $i$，如果 $i$ 是 $n$ 的因子，则递归调用 fac 函数处理 $n/i$。
   • 将因子 $i$ 插入到分解结果的最前面。

3. 输出结果：

   • 在主函数中，调用 fac 函数获得所有分解形式，并格式化输出。

n = int(input())
def fac(n, p): #获取 n 的所有对于每个 1 <= i <= x，都有 a[i] >= p 的分解。
    if n == 1: #当 n 等于 1 时，返回 [[]], 表示 n 只有一种分解且这个分解里面没有数。
        return [[]]
    ans = []
    for i in range(p, n + 1): #遍历 [p, n] 区间内所有整数，并测试它是否可以整除 n。
        if n % i == 0: #如果 i 可以整除 n
            for v in fac(n // i, i): #获取 n / i 的所有对于每个 1 <= j <= x，都有 a[j] >= i 的分解。
                ans.append([i] + v) #把分解追加到答案。
    return ans
ans = fac(n, 2)
for v in ans:
    print(str(n) + "=" + '*'.join(map(str, v)))

Java

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        // 创建一个 Scanner 对象用于接收用户输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取整数 N
        List<List<Integer>> ans = fac(n, 2); // 调用分解函数，初始因子为 2
        for (List<Integer> s : ans) { // 遍历所有分解结果
            System.out.println(list2String(n, s)); // 输出格式化的分解字符串
        }
    }

    // 递归函数，返回所有分解形式
    public static List<List<Integer>> fac(int n, int p) {
        // 基本情况，当 n 为 1 时，返回包含空向量的列表
        if (n == 1) {
            List<List<Integer>> tmp = new ArrayList<>();
            tmp.add(new ArrayList<>()); // 添加空列表表示一种有效的分解
            return tmp;
        }
        
        List<List<Integer>> ans = new ArrayList<>(); // 存储所有分解形式
        // 从最小因子 p 开始遍历可能的因子
        for (int i = p; i <= n; i++) {
            if (n % i == 0) { // 如果 i 是 n 的因子
                // 递归调用寻找 n/i 的分解形式
                List<List<Integer>> next = fac(n / i, i);
                for (List<Integer> list : next) { // 遍历下一层递归返回的结果
                    List<Integer> tmp = new ArrayList<>(list); // 创建新的列表
                    tmp.add(0, i); // 将当前因子 i 插入到列表开头
                    ans.add(tmp); // 保存这条新的分解形式
                }
            }
        }
        return ans; // 返回所有的分解形式
    }

    // 将列表转换为字符串格式
    public static String list2String(int n, List<Integer> numbers) {
        return n + "=" + numbers.stream() // 将列表中的数字转换为字符串
                .map(String::valueOf) // 转换每个整数为字符串
                .collect(Collectors.joining("*")); // 用 "*" 连接字符串
    }
}

c++

#include <iostream>
#include <vector>

using namespace std;

// 递归函数，返回所有分解形式
vector<vector<int>> fac(int n, int p) {
    vector<vector<int>> ans; // 存储所有分解形式的二维向量
    if (n == 1) {
        ans.push_back(vector<int>()); // 当 n 为 1 时，返回空向量表示一种分解
        return ans;
    }
    // 从最小因子 p 开始遍历
    for (int i = p; i <= n; i++) {
        if (n % i == 0) { // 如果 i 是 n 的因子
            // 递归调用，寻找 n/i 的分解形式
            vector<vector<int>> temp = fac(n / i, i);
            // 将当前因子 i 插入到分解结果中
            for (vector<int>& v : temp) {
                v.insert(v.begin(), i); // 将 i 添加到分解的开头
                ans.push_back(v); // 保存这条新的分解形式
            }
        }
    }
    return ans; // 返回所有的分解形式
}

int main() {
    int n;
    cin >> n; // 输入整数 N
    vector<vector<int>> ans = fac(n, 2); // 从 2 开始进行质因分解
    for (vector<int>& v : ans) { // 遍历所有分解形式
        cout << n << "="; // 输出分解式的开头
        for (int i = 0; i < v.size(); i++) {
            if (i > 0) {
                cout << "*"; // 输出乘号
            }
            cout << v[i]; // 输出因子
        }
        cout << "\n"; // 换行
    }
    return 0; // 程序结束
}