蓝桥杯 分解质因数 C语言
程序员文章站
2022-03-08 18:45:33
...
/*
问题描述
求出区间[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<=10000
*/
分析:
首先判断数是否是素数,若是素数,能否将3整除,若不能直接输出,若能,用三分解。若不是素数,那就一直除二直到余数为素数,*这里要注意的是,要对最后剩的素数再次进行判断能否被3整除,这样才能保证因数被分解的很彻底。*
#include <stdio.h>
//素数
void fun1(int i) {
int j;
if(i%3!=0)
printf("%d=%d",i,i);
else {
printf("%d=3*",i);
for(j=i/3; j%3==0&&j!=3; j/=3)
printf("3*");
printf("%d",j);
}
}
//非素数
void fun2(int i) {
int j;
printf("%d=",i);
printf("2*");
for(j=i/2; j%2==0&&j!=2; j/=2)
printf("2*");
if(j%3==0&&j!=3) { //对素数进行再次判断
printf("3*");
for(j=j/3; j%3==0&&j!=3; j/=3)
printf("3*");
printf("%d",j);
} else
printf("%d",j);
}
int main() {
int a,b,i,j;
scanf("%d%d",&a,&b);
if(a>10000||a<2||b>10000||b<2)//限制条件
return 0;
for(i=a; i<=b; i++) {
if(i==2||i==3)
printf("%d=%d",i,i);
else {
if(i%2!=0) //素数
fun1(i);
else//非素数
fun2(i);
}
printf("\n");
}
return 0;
}