蓝桥杯【基础练习】分解质因数——C++

小半 • 2023年2月7日上午10:13 • 技术随笔 • 阅读 479

问题描述

求出区间[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

解题思路：

（1）首先明白何为质因数？顾名思义，既是质数，又是因数

（2）区间内本身就是质数的整数n无需分解，直接输出n=n

（3）其次就是讨论区间内不是质数的整数。因为待分解整数能分解出来的质因数个数是未知的，可能是两项之积，也可能是三项、四项……之积，所以我们要将最后分解的等式“拼凑”出来。

具体说明：就是一个数在从2开始判断是否为其质因数，如果是那么就除尽2的因数，那么接下来循环能被除尽2整除的数，这个数必定是原数的质因数，依次类推。例如输入的数n=100，那么从2开始判断是否是100的质因数，明显2是100的质因数，那么就一直除以2，100/2=50,50/2=25，直到不能整除为止，接下来继续进行循环对3,4…进行整除，此时n=25不能整除3，4，跳到了5。25/5=5，那么5也是100的质因数。接着25/5=5,5/5=1,1/5不是整除。此时i=1<j=5，for循环条件不满足，循环结束，最终得到100=2*2*5*5

完整代码

#include<iostream>
#include<math.h>
using namespace std;
//判断素数 
int isPrime(int n){
	if(n==1)
	  return 1;
	else{
		for(int i=2;i<=sqrt(n);i++){
	  		if(!(n%i))
	  		  return 0;
	  	}
	  	return 1;
	}
} 

int main(){
	int a,b;
	cin>>a>>b;
	for(int i=a;i<=b;i++){
		//如果本身就是素数，则无需分解 
		if(isPrime(i))
		  cout<<i<<"="<<i<<endl;
		else{
			cout<<i<<"=";//因为该整数质因数个数未知，先输出前段部分 
			int t=i;
			int j=2;
			//开始分解质因数 
			while(t>1){
				if(!(t%j)){
					t=t/j;
					cout<<j;
					//当t=1时则说明已经分解到最后一项，无需再加 * 号 
					if(t!=1)
					  cout<<"*";
				} 
				else{
					j++;
				}
			}
			cout<<endl;
		}
	}
	return 0;
}