05 August 2008
给一个正整数n，寻找n的从小到大的所有整除的因子的第k大个，从1开始
枚举O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int kthFactor(int n, int k) {
for(int i = 1; i <= n; i++) {
if(n % i == 0) {
k--;
if(k == 0) {
return i;
}
}
}
return -1;
}
}
优化 O(logn)
如果 n 有一个因子 k，那么它必然有一个因子 n/k，这两个因子中至少有一个是小于等于 \sqrt n 的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int kthFactor(int n, int k) {
int count = 0, factor;
for (factor = 1; factor * factor <= n; ++factor) {
if (n % factor == 0) {
++count;
if (count == k) {
return factor;
}
}
}
--factor;
if (factor * factor == n) {
--factor;
}
for (; factor > 0; --factor) {
if (n % factor == 0) {
++count;
if (count == k) {
return n / factor;
}
}
}
return -1;
}
}