C 语言第25题：分解质因数（输出 90=2×3×3×5 形式）

题目

从标准输入读入一个大于 1 的正整数 n，将其分解为质因数乘积的形式输出（例如：90=2*3*3*5）。

输入格式：一行输入一个正整数 n。

输出格式：按 n=p1*p2*...*pk 的格式输出质因数分解结果，末尾换行。

数据范围与约定：2 ≤ n ≤ 10⁹。

思路与算法

1. 试除法原理
从最小质数 d = 2 开始试除。若 x % d == 0，则 d 必为质因子，循环除尽该因子并格式化输出，然后 d++。

2. 范围缩减到 √x
因数试除只需进行到 d * d ≤ x。循环结束后若 x > 1，则剩余的 x 本身就是一个大于 √n 的质因数，直接追加输出即可。

完整程序

#include <stdio.h>

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 2) {
        return 1;
    }

    int first = 1;
    printf("%d=", n);
    int x = n;

    // 试除法只需进行到 d * d <= x
    for (int d = 2; d * d <= x; d++) {
        // 反复除尽当前质因子 d
        while (x % d == 0) {
            if (!first) {
                putchar('*');
            }
            printf("%d", d);
            first = 0;
            x /= d;
        }
    }

    // 若最后剩余的 x > 1，说明它本身是一个大于 √n 的质数
    if (x > 1) {
        if (!first) {
            putchar('*');
        }
        printf("%d", x);
    }
    putchar('\n');
    return 0;
}

运行示例

输入：

90

输出：

90=2*3*3*5