算法学习【10】寻找质因数的个数

题目如下：

       注意：最多只有一个质因子大于sqrt(n)，若有两个这样的质因子，则它们相乘>n，所以不存在。如果i+=1这样不停相除寻找，只需要到刚大于sqrt(n)即可。

      可以时间换空间，存储一部分小的常用质因子。

      大于2的偶数肯定不是质因子，可以 用j+=2寻找较大的质因子。

      代码：

import java.util.Scanner;

public class Main{
    public static int N[] = new int[]{2,3,5,7,11,13,17,19,23,29};
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            int num = sc.nextInt();
            int temp = (int)Math.sqrt(num);
            int count=0;
            int i=0;
            int j=31;//由已知质因子数组N决定

            while(num>1){
                //先解决已知的质因子
                if(i<N.length){
                    while(num%N[i]==0){
                        num /= N[i];
                        count++;
                    }
                    i++;
                }else{
                    while(num%j==0){
                        num /= j;
                        count++;
                    }
                    j += 2;//大于2的偶数肯定不是质因子
                    if(j>temp)
                        break;
                }
            }

            if(num>1)
                count++;
            System.out.println(count);
        }
    }
}