桐桐的数学难题
题目描述
今天数学课上,桐桐学习了质数的知识:一个正整数如果只能被1和它本身整除,那么这个整数便是质数。桐桐就想:任意一个正整数是否都能分解成若干个质数相乘的形式呢?输入一个正整数n(2≤n≤109),把它分解成质因子相乘的形式,如果为质数则输出该数本身。如:36=2×2×3×3;19=19。你能帮助桐桐解决这个难题吗?
输入
输入一个正整数n(2≤n≤109)
输出
把它分解成质因子相乘的形式,如果为质数则输出该数本身,乘数从小到大输出。
样例输入
99
样例输出
99=3311
import java.util.ArrayList;
import java.util.Scanner;
public class 桐桐得数学题 {
static int n;
// static ArrayList<Integer> list = new ArrayList<Integer>();
static boolean isPrime(int i) {
// if(list.contains(i)) return true;
// if(i<list.get(list.size()-1)) return false;
if (i < 2) return false;
if (i == 2) return true;
for (int j = 2; j <= (int) Math.sqrt(i); j++) {
if (i % j == 0) return false;
}
// list.add(i);
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// list.add(2);
n = sc.nextInt();
if(isPrime(n)){
System.out.println(n+"="+n);
return ;
}
StringBuilder sb = new StringBuilder(n + "=");
int a = 1;
int max=(int) Math.sqrt(n);
for (int i = 2; i <= max; i++) {
if (n % i == 0 ) {
// int b = n;
while (n % i == 0) {
a *= i;
sb = sb.append(i).append("*");
// System.out.println(sb);
n /= i;
}
max=(int) Math.sqrt(n);
// if (a == n) {
// System.out.println(sb.delete(sb.length() - 1, sb.length()));
// return;
// }
}
}
if(n==1){
sb.delete(sb.length() - 1, sb.length());
}
else
sb.append(n);
System.out.println(sb);
}
}