蓝桥杯练习系统基础练习（vip试题）：BASIC-16 分解质因数

约定不等于承诺〃 2023-05-21 07:16 22阅读 0赞

### 文章目录 ###

*  题目信息
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  样例输入
     *  样例输出
     *  提示
     *  数据规模和约定
 *  解题思路
 *   *  主要考察
     *  解题思路
     *  解题代码

# 题目信息 #

## 问题描述 ##

求出区间\[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的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。最小的合数是4。  
 这里就不得不提到一个关于分解质因数的定理：`唯一分解定理：又称为正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。`比如12和18,12的因数有：1、2、3、4、6、12，可以分解成好几种数的乘积：`1*12，3*4，2*6,2*2*3`。18的因数有：1、2、3、6、9、18，同样也可以写成好几种数的乘积，但是这些种类中都有比较特别的一组：分别是：`12 = 2*2*3`,`18 = 2*3*3`,12与18都可以分成几种形式不同的乘积，但`分成质因数连乘积`就只有以上一种，而且不能再分解了。你会发现这一组`全部都是他们的质因数组成的乘积`，由于是质因数当然就不可以再进行分解。通常我们分解质因数的方法有以下几种：

*  短除法：

>  从最小的质数除起，一直除到结果为质数为止。

*  相乘法

>  写成几个质数相乘的形式（这些不重复的质数即为质因数），实际运算时可采用逐步分解的方式。如：`36=2*2*3*3 运算时可逐步分解为36=4*9=2*2*3*3或3*12=3*2*2*3`

## 解题思路 ##

通过上面的解释，相信我们已经对分解质因数有了一个比较全面的了解。但是我们具体怎样实现呢？由于短除法在代码中比较容易实现，所以我们使用短除法进行质因数分解。我们将每一个数从2开始除，因为2是最小的质数。对n进行分解质因数，应先找到一个最小的质数**j**，然后按下述步骤完成：  
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。  
(2)如果n>**j**，但n能被**j**整除，则应打印出**j**的值，并用n除以**j**的商,作为新的正整数n，重复执行第一步。  
(3)如果n不能被j整除，则用**j**\+1作为**j**的值,重复执行第一步。  
该方法又叫做：Pollard Rho快速因数分解，是由John M. Pollard于1975年提出的，该算法时间复杂度为O（n^(1/4)）。  
比如360的分解过程为：  
![360分解质因数过程][360]

## 解题代码 ##

#include<iostream>
    using namespace std;
    
    int main(){ 
    	int a,b;
    	cin>>a>>b;
    	for(int i=a;i<=b;i++){ 
    		int n = i; 
    		cout<<n<<"=";
    		for(int j=2;j*j <= n;j++){ 
    			while(n%j == 0){ 
    				n = n/j;
    				cout<<j;
    				if(n!=1)  cout<<"*";
    			}
    		}
    		if(n!=1)  cout<<n;
    		cout<<endl;
    	}
    	
    	return 0;
    
    }

--------------------

>  以上就是对于本题的解题思路了。如果你觉得我的文章对你有用请点个赞支持一下吧，喜欢我写的文章那么请点个关注再走哟。如果此文章有错误或者有不同的见解欢迎评论或者私信。  
> ![上号！][20200429215234464.png]  
> 我是ACfun：一个成长中的程序猿，感谢大家的支持。

[360]: /images/20230521/281ee9aeb0774a50a3b9319d5c552253.png
[20200429215234464.png]: /images/20230521/e2ed8403a20046a3ab241e7f1c41ede1.png