What is the key insight to solve the Three Divisors problem?

The key insight is recognizing that a number with exactly three divisors must be the square of a prime number.

How can I optimize the divisor counting method for this problem?

You can optimize the divisor counting by only checking divisors up to the square root of n.

What pattern does the Three Divisors problem test?

It tests your understanding of divisors and number theory, specifically the properties of squares of prime numbers.

What is the time complexity of the brute force approach?

The time complexity of the brute force approach is O(n), as it requires checking every number up to n.

Can n be larger than 10^4?

The problem constraint is 1 <= n <= 10^4, but variations may test larger values of n.

#1952

Easy

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

三除数

给你一个整数 n 。如果 n 恰好有三个正除数，返回 true ；否则，返回 false 。如果存在整数 k ，满足 n = k * m ，那么整数 m 就是 n 的一个除数。示例 1：输入： n = 2 输出： false 解释： 2 只有两个除数：1 和 2 。示例 2：输入： …

数学枚举数论

题目描述

给你一个整数 n 。如果 n 恰好有三个正除数 ，返回 true ；否则，返回 false 。

如果存在整数 k ，满足 n = k * m ，那么整数 m 就是 n 的一个除数。

示例 1：

输入：n = 2
输出：false
解释：2 只有两个除数：1 和 2 。

示例 2：

输入：n = 4
输出：true
解释：4 有三个除数：1、2 和 4 。

提示：

1 <= n <= 10⁴

lightbulb

解题思路

方法一：枚举

一个数 $n$ 一定有 $1$ 和 $n$ 两个正除数，因此只需要枚举 $2$ 到 $n-1$ 之间的数，看它们是否是 $n$ 的正除数即可，是则累加计数器，最后判断计数器是否为 $1$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为给定的整数。

1

2

3

4

class Solution:
    def isThree(self, n: int) -> bool:
        return sum(n % i == 0 for i in range(2, n)) == 1

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
This problem tests understanding of divisors and properties of numbers.
question_mark
Look for efficient approaches that minimize unnecessary calculations.
question_mark
The candidate should recognize patterns in the number's divisors and use optimizations such as prime checking.

warning

常见陷阱

外企场景

error
Forgetting that n must be the square of a prime number to have exactly three divisors.
error
Incorrectly counting the divisors of non-perfect squares.
error
Missing optimizations that improve runtime, such as only checking divisors up to √n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Test with larger values of n, such as 10^4.
arrow_right_alt
Consider n values that are squares of prime numbers.
arrow_right_alt
Examine cases where n has more than three divisors.

help

常见问题

外企场景

继续练习

#2427 公因子的数目 #2761 和等于目标值的质数对 #2947 统计美丽子字符串 I