How do I identify numbers with exactly four divisors efficiently?

Check if a number is either a product of two distinct primes or a cube of a prime, which guarantees exactly four divisors.

Does the solution handle repeated numbers in the array?

Yes, each occurrence of a number with four divisors contributes to the sum independently.

What is the maximum divisor check needed for numbers in nums?

Only check up to the square root of each number; paired divisors account for the rest.

Can this problem be solved without checking all divisors?

Yes, using the mathematical pattern for numbers with exactly four divisors avoids full enumeration.

Why is this considered an Array plus Math problem?

Because it combines array traversal with mathematical recognition of divisor patterns to compute sums efficiently.

#1390

Medium

auto_awesome数组·数学

LeetCode 题解工作台

四因数

给你一个整数数组 nums ，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。示例 1：输入： nums = [21,4,7] 输出： 32 解释： 21 有 4 个因数：1, 3, 7, 21 4 有 3 个因数：1, 2, 4 7 有 2 个…

数组数学

题目描述

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

示例 1：

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

示例 2:

输入: nums = [21,21]
输出: 64

示例 3:

输入: nums = [1,2,3,4,5]
输出: 0

提示：

1 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：因数分解

我们可以对每个数进行因数分解，如果因数的个数为 $4$ 个，那么这个数就是符合题意的数，我们将其因数累加到答案中即可。

时间复杂度 $O(n \times \sqrt{n})$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def f(x: int) -> int:
            i = 2
            cnt, s = 2, x + 1
            while i <= x // i:
                if x % i == 0:
                    cnt += 1
                    s += i
                    if i * i != x:
                        cnt += 1
                        s += x // i
                i += 1
            return s if cnt == 4 else 0

        return sum(f(x) for x in nums)

speed

复杂度分析

指标	值
时间	complexity varies by method: brute-force is O(n _sqrt(m)) for array size n and max element m, while pattern-based checking can approach O(n_ log m). Space complexity is O(1) beyond input storage, as no extra arrays are needed.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for recognition that exactly four divisors have a prime-product pattern.
question_mark
Expect early termination once a number exceeds four divisors.
question_mark
Interest in distinguishing brute-force versus optimized math approaches.

warning

常见陷阱

外企场景

error
Assuming all numbers need full divisor enumeration without pruning.
error
Forgetting that numbers can repeat and each instance contributes to the sum.
error
Counting numbers with fewer or more than four divisors by mistake.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count numbers with exactly three divisors instead of four.
arrow_right_alt
Return only the sum of numbers themselves, not their divisors.
arrow_right_alt
Apply the problem to a 2D array where each row is treated as nums.

help

常见问题

外企场景

继续练习

#1406 石子游戏 III #1363 形成三的最大倍数 #1352 最后 K 个数的乘积