分解质因数的误区
误区
我原来的想法是找到除数范围内的所有质因数，建立了一个素数筛，然后逐个便利判断是是除数的引述，很是麻烦，而且时间复杂度高，大致为O(n)级别代码如下：
import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class 分解质因数 { static Set<Integer> set=new HashSet<Integer>(); static List<Integer> list=new ArrayList<Integer>(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); shai(n);//素数筛 int temp=n; while(temp!=1) { for (int k : set) { if(temp%k==0) { temp/=k; list.add(k); break; } } } System.out.print(n+"="); for (int i = 0; i < list.size()-1; i++) { System.out.print(list.get(i)+"*"); } System.out.println(list.get(list.size()-1)); } private static void shai(int n) { boolean a[]=new boolean [n+1]; for (int i = 2; i < a.length; i++) { if(!a[i]) { for (int j = 2*i; j < a.length; j+=i) { a[j]=true; } } } for (int i = 2; i < a.length; i++) { if(!a[i]) { set.add(i);//筛，储存在map中 } } } }
正解
但是这种打表的时间复杂度太高了，可从从2开始便利，如果有能除以2，就继续出2，直到把2除尽了，然后后面4，6，8就不能作为因数了。3，5，7同理，代码如下：
import java.util.Scanner; /* * 此题我做的时候出现了一个误区，就是认为需要找出这个数字之内的所有质因数 * 就是说需要判断除数是不是都是质因数，但是完全不需要如此 * 因为如果2都除尽了，就不再有4，6，8。3同理。。。。 * * */ public class 分解质因数2 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int temp=n; System.out.print(n+"="); for (int i = 2; i <=n; i++) { if(temp%i==0) { System.out.print(i); temp/=i; if(temp==1) break;//当，所有质因数找到之后，结束循环 i--;//保持因数不变，继续除干净 System.out.print("*"); } } } }
