[数据结构与算法]C语言分解因式含源码测试

题目再现

一个正整数可分解为几个因数的乘积，例如,$6=1\times 2\times 3,7=1\times 7$.设计一个算法，给定一个整数范围$[A,B]$,计算并输出a和b范围内的每一个正整数的因数乘积.

解决题目核心思想

对于范围[a,b]内的每一个整数i,代之以s，用$1?i/2$的整数j试除s，如果能够整除s，j就是i的一个因数，然后修改s为它整除j的结果，继续试除直到s为1.一个特殊情况是i为素数，它只能被1和自身整除，在确定1为它的因数后，补充输出i自身即可；另一种特殊情况是i用1-i//2的整数j试除后，还欠缺一个因数，需要补充输出最后一个因数。

代码测试效果

完整源码

#include<stdio.h>
void factorization(int a,int b) {
    int i,j,s= 0;
    for(i=a;i<=b;i++){
        s= i;
        printf("%d=",i);
        while(s!=1) { //按照解题思路求解
            for(j=1;j<=i/2;j++)
                if(s%j==0){
                    printf("%d",j);
                    s = s/j;
                    if(s!=1)
                        printf("*");
                    else
                        printf("\n");
                }
            if(s==i || j>i/2 && s != 1) //素数情景辨别
            {
                printf("%d\n",s);
                s = 1;
            }
        }
    }
}
int main() {
    int a,b;
    printf("请输入一个整数范围a..b,要求a<b\n");
    scanf("%d, %d",&a,&b);
    factorization(a,b);
    printf("\n");
    return 0;

}

参考文献

殷人昆著.数据结构与算法解析.北京：清华大学出版社，2021.4