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,并判断是否能整除,如此反复地做除法,直到不能再整除为止。

算法描述

图 1:N-S 图描述

在此算法中,每整除一次后,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