蓝桥杯 BASIC-16 基础练习 分解质因数
问题描述
求出区间[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

代码如下：

#include<bits/stdc++.h>
using namespace std;
bool check(int n)
{   if(n <= 1) return false;//0，1不是质数也不是合数，因式分解时，1当为质数if(n == 2 || n == 3) return true;if(n %6 != 1 &&n %6 != 5)return false;for(int i = 5;i<=sqrt(n);i+=6){if(n % i ==0 || n %(i+2)==0)//5，7return false;}return true;
}
int main()
{int a,b;cin>>a>>b;for(int i = a;i <= b;i++){cout<<i<<"=";if(check(i) == true){cout<<i<<endl;continue;  	}int j = i;do{for(int k = 2;k<=sqrt(j);k++){if(j % k == 0){cout<<k<<"*";j = j/k;break;}}if(check(j) == true)cout<<j<<endl;}while(check(j) == false);}return 0;
}