C语言分解质因数（质因子）

这是一个C语言 do while 循环示例：把正整数 n 分解成质因数相乘的形式。例如 24=2×2×2×3。

问题分析

输入：一个正整数n。

输出：形如 24=2×2×2×3 的质因子相乘的形式。

本题中我们需要重复判断从 2 开始而且小于 n 的每一个自然数 i 是否是正整数 n 的因数，而一个正整数有多少个质因子，也是不确定的，因而我们可以选用 do-while 语句来解决该问题。

此外，一个正整数可能会有多个相同的质因子，因此在确定 i 是 n 的质因子以后，还需要判断 n 有几个质因子 i。为此，我们还需要用 while 语句来做循环，用一个质因子反复地做除法，找到所有相同的质因子，直到不能再整除为止。

实际上我们用到了循环语句的嵌套，外层的 do-while 循环语句用于判断从 2 开始的每一个 i 是否是正整数 n 的因数，如果 i 是 n 的因数，则在内层循环 while 语句中用整除得到的商再次除以 i，并判断是否能整除，如此反复地做除法，直到不能再整除为止。

算法描述

在此算法中，每整除一次后，n 值都被替换为整除后的商，继续参加整除，直到不能再整除为止。这个不能再被整除的 n 同样是原来的正整数的一个质因子。

i 从 2 开始，逐渐递增并反复参加整除的过程中，能够被整除的 i 一定是一个质因子，不会出现非质因数。

代码清单 1：把正整数 n 分解成质因子相乘的形式

#include <stdio.h>
#include <stdlib.h>
int main( )
{
    int n,i=2;
    printf("输入一个正整数：\n");
    scanf("%d",&n);
    printf("%d=",n);
    do
    {
        while(n % i == 0)        //如果 i 是n的质因子，则反复分解出 i
        {
            printf("%d*",i);     //输出质因子和一个乘号
            n /= i;              //n = n / i,用整除后的商作为新的被除数
        }
        i++;                     //生成新的i
    }while(i<n);
    printf("%d\n",n);            //输出最后一个质因子 n
    system("pause");
    return 0;
}

运行结果：

输入一个正整数：
72
72=2*2*2*3*3*1