长整数的因子分解

练习题做多了就发现有好多整数相关的题目都要用到因子分解（或是其变种，如整除之类），比如有一个题：给定整数N，若N可以分解为四个整数乘积，我们称其级别为1，如果上述分解的因子每个都能进行同样的分解，我们称N级别为2，依次类推，求任意N的级别

 

我的思路是设立一个全局变量count 通过递归函数进行N的逐步整除，每次整除count都要加1，通过count控制在4以内结束递归，然后对N的每个因子进行类似处理。类似于上一篇博客的问题。大致代码如下（未完成）：

   void  countFactor(long n)
    {

       for(int i=2;i<n;i++)       {
           if(n%i==0)
           {
               count++;
               countFactor(n/i);
               break;
           }       
    }
}

后来我发现这样做行不通，不说最后能否运行，但是复杂度就已经惊人，最差为N！级别

最近好像很迷信递归，但这个题来讲递归不是好办法。

接下来参考其他人的算法，确实让我开了眼界。该程序来自stubbscroll，如果我的考虑是自上而下，他的做法应该是自下而上，先将N分解为质因子，通过计算质因子数可以多少次被4除就能判定N的级别了。非常简洁，复杂度应该为O(NlogN)

一下为代码：

 public int getLevel(long N) {
        //exellent! 先进行因式分解，分解到质因子，然后将这些因子四个一堆进行分类有多少个四分结果就是多少
        int num = 0;
        while (N % 2 < 1) {
            N /= 2;
            num++;
        }
        for (int i = 3; (long) i * i <= N; i += 2) {
            while (N % i == 0) {
                N /= i;
                num++;
            }
        }
        if (N > 1) {
            num++;
        }
        int ans = 0;
        while (num > 3) {
            num /= 4;
            ans++;
        }
        return ans;
    }
}