欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-12 20:53:18
...

质因数分解

问题描述   求出区间[a,b]中所有整数的质因数分解。
输入格式   输入两个整数a,b。
输出格式   每行输出一个数的分解,形如k=a1a2a3…(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. 短除法
    从最小的质数除起,一直除到结果为质数为止。【蓝桥杯】质因数分解java题解
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);
		}
		
	}

}
相关标签: 蓝桥杯 eclipse