# 1492. The kth Factor of n

• Time: $O(\sqrt{n})$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int kthFactor(int n, int k) { // If i is a divisor of n, then n / i is also a divisor of n. So, we can // find all the divisors of n by processing the numbers <= sqrt(n). int factor = 1; int i = 0; // i-th factor for (; factor * factor < n; ++factor) if (n % factor == 0 && ++i == k) return factor; for (factor = n / factor; factor >= 1; --factor) if (n % factor == 0 && ++i == k) return n / factor; return -1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int kthFactor(int n, int k) { // If i is a divisor of n, then n / i is also a divisor of n. So, we can // find all the divisors of n by processing the numbers <= sqrt(n). int factor = 1; int i = 0; // i-th factor for (; factor * factor < n; ++factor) if (n % factor == 0 && ++i == k) return factor; for (factor = n / factor; factor >= 1; --factor) if (n % factor == 0 && ++i == k) return n / factor; return -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def kthFactor(self, n: int, k: int) -> int: # If i is a divisor of n, then n // i is also a divisor of n. So, we can # find all the divisors of n by processing the numbers <= sqrt(n). factor = 1 i = 0 # i-th factor while factor < int(math.sqrt(n)): if n % factor == 0: i += 1 if i == k: return factor factor += 1 factor = n // factor while factor >= 1: if n % factor == 0: i += 1 if i == k: return n // factor factor -= 1 return -1