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

题目

分解质因数（输出 90=2×3×3×5 形式）

思路

从 p=2 开始，while (n>1 && p*p<=n)：若 n%p==0 则输出因子并除尽；否则 p++（或先处理 2 再只试奇数）。

解题分析

从 2 试除，能整除就输出因子并 n/=d，同一 d 可能输出多次（如 3×3）。循环到 d*d>n 后若 n>1，剩余 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;
    for (int d = 2; d * d <= x; d++) {
        while (x % d == 0) {
            if (!first) {
                putchar('*');
            }
            printf("%d", d);
            first = 0;
            x /= d;
        }
    }
    if (x > 1) {
        if (!first) {
            putchar('*');
        }
        printf("%d", x);
    }
    putchar('\n');
    return 0;
}

运行示例

输入：

90

输出：

90=2*3*3*5