基础算法练习：分解质因数

心已赠人 2023-10-04 17:47 53阅读 0赞

## 基础练习 分解质因数（蓝桥杯VIP真题BASIC-16） ##

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

资源限制  
内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

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

问题描述  
　　求出区间\[a,b\]中所有整数的质因数分解。

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

输入格式  
　　输入两个整数a，b。

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

输出格式  
　　每行输出一个数的分解，形如k=a1*a2*a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)

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

样例输入  
3 10

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

样例输出  
![在这里插入图片描述][3979735b2c9445dab7fc94df1ca723d3.png]

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

提示  
　　先筛出所有素数，然后再分解。

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

数据规模和约定  
　　2<=a<=b<=10000

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

思路：

> **质数**：一个数除了1和它本身没有其他的因数，就叫质数。如2，3，5，7，  
> 分解质因数定义：**把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。**  
> ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAaW5maW5pdGVfZGVidWc_size_13_color_FFFFFF_t_70_g_se_x_16]  
> 注意输出格式：k=a1*a2*a3…(a1<=a2<=a3…，k也是从小到大的  
> 构建算法：  
> (1)如果这个质数恰等于i，则说明分解质因数的过程已经结束，打印出即可。  
> (2)如果i>k，但n能被k整除，则应打印出k的值，并用n除以k的商作为新的正整数n，重复执行(1))。  
> (3)如果i不能被k整除，则用k+1作为k的值，重复执行(1)。

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

题解：

import java.util.Scanner;
    public class Main {
       
        
        /**
         * (1)如果这个质数恰等于i，则说明分解质因数的过程已经结束，打印出即可。
         * (2)如果i>k，但n能被k整除，则应打印出k的值，并用n除以k的商作为新的正整数n，重复执行(1))。
         * (3)如果i不能被k整除，则用k+1作为k的值，重复执行(1)。
         */
        public static void main(String[] args

[3979735b2c9445dab7fc94df1ca723d3.png]: https://img-blog.csdnimg.cn/3979735b2c9445dab7fc94df1ca723d3.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAaW5maW5pdGVfZGVidWc_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4eb6f9e47eb74938b28ef3acd22ef091.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAaW5maW5pdGVfZGVidWc=,size_13,color_FFFFFF,t_70,g_se,x_16