如何获取正整数拆分为等规模分组的所有组合及C语言实现方法

实现逻辑 #

你要求的等规模分组本质是找出正整数n的所有小于n的正约数，每个约数对应一个合法分组方案：约数为每组的元素个数，n除以约数的结果为分组总数，完全匹配你给出的示例规则。

C语言实现代码 #

#include <stdio.h>

int main() {
    int n;
    printf("请输入正整数（气球总数）：");
    scanf("%d", &n);

    // 输入合法性校验
    if (n <= 0) {
        printf("输入错误，请输入大于0的正整数\n");
        return 1;
    }

    printf("所有合法的等规模分组方式：\n");
    int schemeCount = 0;
    // 倒序遍历匹配示例输出顺序，如需按每组规模从小到大输出改为正序遍历即可
    for (int perGroup = n - 1; perGroup >= 1; perGroup--) {
        if (n % perGroup == 0) {
            schemeCount++;
            printf("%d. 每组%d个气球，共%d组\n", schemeCount, perGroup, n / perGroup);
        }
    }

    return 0;
}

优化说明 #

如果需要处理极大数值的场景，可将循环上限改为sqrt(n)，每找到一个合法的每组规模k，同时输出每组k个共n/k组和每组n/k个共k组两个结果（注意排除k等于n/k的重复场景），可以将时间复杂度从O(n)降低到O(√n)，大幅提升大数场景的运行效率。

内容的提问来源于stack exchange，提问作者Dhanraj Nimbalkar