蓝桥杯C语言算法：分解正整数的高效实现

1. 项目背景与核心需求

这道蓝桥杯省赛B组题目考察的是C语言基础编程能力和数学思维的综合运用。题目要求我们找出所有可以被分解为两个不同正整数乘积的正整数，并按特定格式输出结果。这类题目在算法竞赛中非常典型，既考察了循环控制、条件判断等基础语法，又需要选手具备将数学问题转化为程序逻辑的能力。

在实际比赛中，这类题目往往作为基础题出现，但想要高效准确地完成，需要掌握几个关键点：如何设计合理的遍历范围、如何避免重复计算、如何优化判断条件。我在辅导学生备战蓝桥杯时发现，很多初学者容易在这类问题上陷入暴力枚举的陷阱，导致程序效率低下或者输出格式不符合要求。

2. 问题分析与算法设计

2.1 数学建模

题目本质是寻找所有满足n = a×b（a≠b）的正整数n。从数学角度看，这意味着n必须是非素数且不是完全平方数。因为：

• 素数只能分解为1×n
• 完全平方数可以分解为a×a

因此有效的n必须至少有两组不同的因数对。例如12可以分解为：

• 1×12
• 2×6
• 3×4

2.2 算法选择

最直观的方法是双重循环暴力枚举：

1. 外层循环遍历所有可能的n
2. 内层循环检查n是否能分解为两个不同数的乘积

但这种O(n²)复杂度的方法效率太低。我们可以优化为O(n√n)的单层循环：

c复制for(int n=1; n<=N; n++) {
    int count = 0;
    for(int a=1; a*a<n; a++) {
        if(n%a == 0) {
            int b = n/a;
            if(a != b) count++;
        }
    }
    if(count >= 2) {
        // 符合条件
    }
}

2.3 边界条件处理

需要特别注意几个特殊情况：

1. 1的处理（1不能分解为两个不同正整数）
2. 素数的排除
3. 完全平方数的特殊处理（如9=3×3不算有效分解）

3. 完整实现代码

c复制#include <stdio.h>

int is_decomposable(int n) {
    int count = 0;
    for(int a=1; a*a<n; a+