蓝桥杯|蓝桥杯 BASIC-16 试题 基础练习 分解质因数

资源限制
时间限制:1.0s 内存限制:512.0MB
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a,b。
输出格式
每行输出一个数的分解,形如k=a1a2a3…(a1<=a2<=a3…,k也是从小到大的)(具体可看样例)

样例输入
3 10
样例输出
3=3
4=22
5=5
6=2
3
7=7
8=222
9=33
10=2
5
提示

先筛出所有素数,然后再分解。
【蓝桥杯|蓝桥杯 BASIC-16 试题 基础练习 分解质因数】数据规模和约定
2<=a<=b<=10000

#define _CRT_SECURE_NO_WARNINGS 1#include #include using namespace std; const int N = 10000; int a, b; int arr[N]; int index; bool isprime(int n) { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return 0; } return 1; }int main() { cin >> a >> b; for (int i = 2; i <= b; i++)//筛选素数,并将其放到数组中保存起来 { if (isprime(i)) { arr[index] = i; index++; } } for (int i = a; i <= b; i++) { cout << i << "="; int num = i; for (int j = 0; j < index; j++) { while (num % arr[j] == 0) { num /= arr[j]; cout << arr[j]; if (num == 1) { cout << endl; break; } else cout << "*"; } } } return 0; }

    推荐阅读