分解质因数的应用题及答案(分解质因数的题及答案)

问题描述
　　求出区间[a,b]中所有整数的质因数分解。
输入格式
　　输入两个整数a，b。
输出格式
　　每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=2x2
5=5
6=2x3
7=7
8=2x2x2
9=3x3
10=2x5
提示
　　先筛出所有素数，然后再分解。
数据规模和约定
　　2<=a<=b<=10000

先找质数将质数存到数组中从n-m遍历，如果是质数则打印n=n，如果不是质数，例如6，6=2x3,则用6依次 对数组中质数取模，直到等于0，打印该质数。但是 例如8，8=2x2x2x2,需要8对数组的第一个数一直取模，然后打印质数　。

import java.util.Scanner;

public class 基础练习分解质因数 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int m = input.nextInt();
		int[] zhishu = new int[m + 1];//存储质数
		int[] zhishu2 = new int[m];//存储质数
		int k = 0;//记录质数的个数
		for (int i = 2; i <= m; i++) {
			int a = 0;
			for (int j = 2; j <= Math.sqrt(i); j++) {
				if (i % j == 0) {
					a++;
				}
			}
			if (a == 0) {//找到质数
				zhishu[i] = i;//按质数序号存储质数；
				zhishu2[k++] = i;//按顺序存储质数
			}
		}
		for (; n <= m; n++) {
			if (zhishu[n] == n) {//是质数打印
				System.out.println(n + "=" + n);
			} else {//不是质数
				System.out.print(n + "=");
				int n1 = n;//用n1代替n
				for (int chu = 0; chu < k; chu++) {//按个数便利质数
					while (n1 % zhishu2[chu] == 0) {//如果8=2*2*2，就要一直除
						if (n1 == zhishu2[chu]) {
							System.out.print(zhishu2[chu]);//最后一个因数打印
							n1 = n1 / zhishu2[chu];//打印后再除以质数
						} else if (n1 == 1) {//结束循环
							break;

						} else {
							System.out.print(zhishu2[chu] + "*");//除了最后一个因数打印
							n1 = n1 / zhishu2[chu];//打印后再除以质数
						}
					}
				}
				System.out.println();//换行
			}
		}
	}
}