【蓝桥杯】质因数分解java题解

亦凉 2023-07-06 11:48 3阅读 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.  每个合数都可以写成几个质数相乘的形式
2.  每个合数的质因数分解有且仅有一种
3.  短除法  
    从最小的质数除起，一直除到结果为质数为止。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
    
    class Main
    { 
    	public static void main(String[] args) { 
    		Scanner sc =new Scanner(System.in);
    		int m=sc.nextInt();
    		int n=sc.nextInt();
    		for (int i = m; i <= n; i++) { 
    			System.out.printf("%d=",i);
    			int b = i,k=2;
    			while(k<=Math.sqrt(i)) { //判断质数只需要除到根号这个数
    				if(b%k==0) {         
    					b=b/k;			//短除法b总是商
    					if(b>1) { 
    						System.out.print(k+"*");//没除玩k算一个质因子
    						continue;
    					}
    					else { 
    						System.out.println(k);//刚好相等说明除完了,直接k是最后一个
    					}
    				}
    				k++;//不能整除下一个数,当然这里可以想办法跳过合数比如2,3,5,7这样
    			}//跳出循环说明b是质数
    			if(b==i) System.out.println(i);
    			if(b>1&&b<i)System.out.println(b);
    		}
    		
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200218151413937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx,size_16,color_FFFFFF,t_70