[Google]Return all divisors of n 返回n的所有除数

Google电面:

这个算电面的简单题了. 没帕金森的基本都能写…

其实就是Prime Factorization, 只是code略有不同.  然后这个不是O(n) 算法, 是伪多项式的算法, 因为input和n本身的大小有关系.

public static List<Integer> getAllDivisors(int n) {
		List<Integer> divisors = new ArrayList<Integer>();
		for (int denominator = 1; denominator <=Math.sqrt(n); denominator++)
			if (n % denominator == 0) {
				divisors.add(denominator);
				if (denominator * denominator != n)
					divisors.add(n / denominator);
			}
		Collections.sort(divisors);
		return divisors;
	}

与Prime Factorization的区别就是中间第二个if, 多加了个除数, 仅此而已