基础练习分解质因数

淡淡的烟草味﹌ 2022-06-01 05:35 139阅读 0赞

基础练习 分解质因数

时间限制：1.0s   内存限制：512.0MB

问题描述

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

import java.util.Scanner;
    public class Main {
    	//判断是否为质数（大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；）
    	public static boolean IsPrime(int n){
    		//两个较小数另外处理  
    		if(n==2||n==3)
    			return true;
    		//不在6的倍数两侧的一定不是质数 
    		if(n%6!=1&&n%6!=5)
    			return false;
    		//在6的倍数两侧的也可能不是质数  
    		int tmp =(int)Math.sqrt(n); 
    //      我们通过对一个数进行从2到此数相除，只有1和它本身能除尽而其他数除不尽的数    来判断它是质数		
    //		sqrt(n)表示求平方根，如果在sqrt(n)的左侧找不到约数（除得尽的数），那么在右侧也找不到
    //           所以只需要遍历到sqrt(n)处；
    //		因为大于等于5的质数一定和6的倍数相邻
    //		所以6++快进，
            for(int i=5;i <=tmp; i+=6 )  
                if(n%i==0||n%(i+2)==0 )  
                           return false;
    		return true;
    	}
    	
    
    
    //  分解质因数
    	public static void PrimeFctorization(int n){
            int m=n;
            int flag = 0;
            int[] array = new int[50];
    //        如果不是质数  进行质数分解
            if(!IsPrime(n)){
            	for (int i = 2; i <= n; i++) {
    	            if (n % i == 0) {
    	            	array[flag] = i;
    	                flag++;
    	                n = n / i;
    	                i--;
    	            }
                }
    	        if (flag > 1) {
    	            System.out.print(m + "=" + array[0]);
    	            for (int k = 1; k < flag; k++) 
    	                System.out.print("*" + array[k]);
    	        } 
            }
    //如果是质数
            else
            	System.out.print(n + "=" + n);
    	}
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            for(int i = n; i <= m; i++){
            	PrimeFctorization(i);
            	System.out.println();
            }
          
        }
    }

关于质数的判断请参考： [http://blog.csdn.net/huang\_miao\_xin/article/details/51331710][http_blog.csdn.net_huang_miao_xin_article_details_51331710]

![SouthEast][]

[http_blog.csdn.net_huang_miao_xin_article_details_51331710]: http://blog.csdn.net/huang_miao_xin/article/details/51331710
[SouthEast]: /images/20220601/d8ef6cb232474343b6edce15b8c24788.png