基础练习分解质因数（求出区间[a,b]中所有整数的质因数分解。）

我不是女神ヾ 2023-07-19 12:11 39阅读 0赞

**资源限制**  
时间限制：1.0s 内存限制：512.0MB

## 问题描述 ##

求出区间\[a,b\]中所有整数的质因数分解。  
**输入格式**  
　　输入两个整数a，b。  
**输出格式**  
　　每行输出一个数的分解，形如k=a1*a2*a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)  
**样例输入**  
3 10  
**样例输出**  
3=3  
4=2*2  
5=5  
6=2*3  
7=7  
8=2*2*2  
9=3*3  
10=2*5  
**提示**  
　　先筛出所有素数，然后再分解。  
**数据规模和约定**  
　　2<=a<=b<=1000

## 思路 ##

从区间前端开始一次遍历，在每次遍历时，需要2开始判断，是否为该数的质因数，并设置一个数累加，在循环中判断是否为质数，是否为因数，值得注意的是最后几个判断的条件应当小心。

代码呈上：

#include<stdio.h> 
    #include<math.h> 
    int main()  
    {   
        long int b,i,k,m,n;  
        scanf("%ld%ld",&m,&n);  
        for(i=m;i<=n;i++)  
        {   
            printf("%ld=",i);  
            b = i;k = 2;  
            while(k<=sqrt(i))  
            {   
                if(b%k==0)  
                {   
                    b = b/k;  
                    if(b>1)  
                    {   
                        printf("%ld*",k);continue;  
                    }     
                    if(b==1) printf("%ld\n",k);  
                }  
                k++;  
            }  
            if(b>1&&b<i) printf("%ld\n",b);  
            if(b==i)  
            {   
                printf("%d\n",i);
            }       
        }  
        return 0;  
    }

*运行示例*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70]: /images/20230528/59ce997951744cd2a7e2574223d2145d.png