转自 http://www.cnblogs.com/mengshu-lbq/archive/2012/05/07/2487048.html
如：整数 15，有1， 15， 3，5 共4个因子。要求算法的复杂度为O(sqrt(N)).
首先想到的方法是：逐个枚举，从 1 到 N/2 + 1(当然也可以是 从 1 到 N),这样算法的复杂到至少是O(N)的，
而且，其中还要去重，比如 24 = 4*6 = 6*4，这样还要分配空间来存放找到的因子，并且每次添加的时候，还要
查找是否已经在列表中，采用二分查找也要logN,因此最终的算法复杂度也要达到O(NlogN)。不符合题目的要求。
其实，重复因子的出现是在sqrt(N)的附近，再加上题目给出的算法复杂度的提示，因此我们可以写出如下的算法：
/** * 求正整数 N的因子数 * @param N * @return */public int factors(int N){ if(1 == N) return 1; int count = 2;// 1 与 N 必是 final int sqrt_N = (int)Math.sqrt(N); int r; for(int i = 2; i <= sqrt_N; i++){ if(0 == N % i){ if(i == sqrt_N){ r = N / i; if(r == i){//比如 4 = 2 * 2；那么2 只能算一个 count++; }else{ count += 2; } }else{ count += 2; } } } return count;} /** * 有没有漏掉呢？ * * 假设存在一个正整数 K,使得 K * M = N, 且 K 不在 1, sqrt(N)之间，且M 为正整数 * 那么 M必在(1, sqrt(N))之间，否则 K*M >sqrt(N)*sqrt(N) = N,与 K*M = N矛盾 * 即只要存在两个正整数K, M,使得 K * M = N,那么K， M中必有一个在[1, sqrt(N)]区间中 */ |
注释部分，相当与算法正确性的证明。
当然，如果不调用系统的库函数，可能还需要自己实现求一个整数的平方根的算法，根据本题要求，不要求精度太高，只需要
到 0.1就够了。
扩展：如果N为负数呢？