题面描述:

给定一个整数 $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; // 程序结束
}

给你一个整数$N (1 < N \leq 256)$ ,它的一个分解是$N = a_1 \times a_2 \times a_3 \times ... \times a_x$ , 其中$1 < a_i \leq a_j (i \leq j)$.

对于整数$N$ , 请依次输出每一个分解(按照字典序)

例如,给定整数24,输出是

24=2*2*2*3
24=2*2*6
24=2*3*4
24=2*12
24=3*8
24=4*6
24=24

解答要求 时间限制:C/C++ 1000ms,其他语言:2000ms

内存限制:C/C++ 256MB, 其他语言:512MB

输入

输入只有一个整数$N$

输出

按照字典序，依次输出整数$N$的每一个分解.

样例1

输入

11

输出

11=11

解释

无

样例2

输入

12

输出

12=2*2*3
12=2*6
12=3*4
12=12

解释

无