What is the fastest practical way to solve The kth Factor of n?

For this problem, the cleanest practical solution is to scan up to sqrt(n) and use factor pairs. It cuts unnecessary checks and still lets you return the kth smallest factor in sorted order if you handle the large divisors carefully.

Why does scanning only to sqrt(n) work in this number theory pattern?

If i divides n, then n / i also divides n, so factors come in pairs around sqrt(n). That means every divisor larger than sqrt(n) is paired with one smaller than sqrt(n), so you do not need to test the whole range from 1 to n.

When should I just use the brute-force approach here?

Because n is at most 1000, a simple scan from 1 to n is totally acceptable and often the fastest to code correctly. In an interview, though, you should still mention the factor-pair optimization to show you understand the Math plus Number Theory pattern behind this problem.

What edge case breaks many solutions to The kth Factor of n?

Perfect squares are the main trap. When i * i == n, the pair collapses into one factor, so counting both sides would duplicate the middle divisor and corrupt the kth position.

How do I know when to return -1?

Return -1 when the total number of factors is less than k. In the brute-force version, that means you finish scanning without hitting the kth factor; in the factor-pair version, it means your combined small and large divisor count never reaches k.

#1492

Medium

auto_awesome数学·结合·number·theory

LeetCode 题解工作台

n 的第 k 个因子

给你两个正整数 n 和 k 。如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。考虑整数 n 的所有因子，将它们升序排列。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。示例 1：输入： n = 12, k = 3 输出： …

数学数论

题目描述

给你两个正整数 n 和 k 。

如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。

考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。

示例 1：

输入：n = 12, k = 3
输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。

示例 2：

输入：n = 7, k = 2
输出：7
解释：因子列表包括 [1, 7] ，第 2 个因子是 7 。

示例 3：

输入：n = 4, k = 4
输出：-1
解释：因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。

提示：

1 <= k <= n <= 1000

进阶：

你可以设计时间复杂度小于 O(n) 的算法来解决此问题吗？

lightbulb

解题思路

方法一：暴力枚举

“因子”是指能整除某个数的数。因此，我们只需要从小到大枚举 $[1,2,..n]$ ，找到所有能整除 $n$ 的数，然后返回第 $k$ 个即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        for i in range(1, n + 1):
            if n % i == 0:
                k -= 1
                if k == 0:
                    return i
        return -1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer mentions factors are always between 1 and n, which points to a bounded divisor scan rather than anything probabilistic or recursive.
question_mark
If they ask whether you can do better than checking all numbers up to n, they want the sqrt(n) factor-pair observation.
question_mark
If they stress sorted order, they are testing whether you notice that finding divisor pairs is easy, but returning the kth smallest factor needs careful ordering.

warning

常见陷阱

外企场景

error
Double-counting sqrt(n) when n is a perfect square, which shifts the kth position and returns the wrong factor.
error
Collecting factor pairs but forgetting that large paired divisors appear in reverse order, which breaks the required ascending list.
error
Using zero-based thinking for k and returning one factor too early or too late after decrementing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the full sorted list of factors instead of only the kth one, which makes the factor-pair merge step explicit.
arrow_right_alt
Return the kth largest factor, which uses the same divisor logic but flips how you index the paired divisors.
arrow_right_alt
Handle many queries for different k on the same n, where precomputing the sorted factors once becomes more useful than repeated scans.

help

常见问题

外企场景

继续练习

#1447 最简分数 #1627 带阈值的图连通性 #1250 检查「好数组」