题解 | 质数因子

#include <stdio.h>
#include <math.h>

int main() {
    int a, b;
    scanf("%d",&a);
    for(b=2;b<a;b++){
        if(b>sqrt(a)+1){
            b=a;
        }
        while(a%b==0){
            printf("%d ",b);
            a/=b;
        }
    }
    return 0;
}

核心算法：试除法

质因数分解最常用的方法是试除法：从小到大枚举可能的质因子 b，若 b 能整除当前的 n，则不断除以 b 并输出 b，直到 n 不再被 b 整除。

关键优化

• 枚举时，b 从 2 开始，每次 +1（实际上可以只枚举质数，但本题范围较小，直接枚举整数也足够快）。

算法步骤

1. 读入整数 n。
2. 令 b=2。
3. 当 b×b≤n 时循环：如果 n%b==0：输出 b（带空格），并令 n=n/b，重复此步骤直到 n不再被 b 整除。否则 b=b+1。
4. 循环结束后，如果 n>1，说明剩余的 n 是一个大于 原n​ 的质因子，直接输出它。
5. 输出换行（若需要）。

示例模拟

以 n=84为例：

• b=2，84%2=0 → 输出2，n=42；42%2=0 → 输出2，n=21；21%2≠0 → b=3
• b=3，21%3=0 → 输出3，n=7；7%3≠0 → b=4
• b=4，4×4=16 >7，循环结束
• 剩余 n=7 >1 → 输出7最终输出：2 2 3 7