难度: Easy
给你一个整数 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 <= 104
Submission
运行时间: 23 ms
内存: 16.1 MB
class Solution:
def isThree(self, n: int) -> bool:
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
k = int(n**0.5)
if n >3 and k**2 == n and is_prime(k):
return True
return False
Explain
题解的核心思想是利用数学性质来判断一个数恰好有三个正除数。具体来说，一个数n如果恰有三个正除数，则这三个数一定是1、k和k^2，其中k必须是质数。这是因为非质数的因数会超过两个，从而使得除数总数超过三个。因此，算法首先计算k=n的平方根，然后检查k^2是否等于n来确认是否只有两个除数：k和k^2。接着，使用辅助函数is_prime来检查k是否为质数。如果k是质数并且k^2等于n，则n有三个除数（1, k, k^2），否则不是。
时间复杂度: O(sqrt(sqrt(n)))
空间复杂度: O(1)
# Solution class to determine if a number has exactly three divisors
class Solution:
def isThree(self, n: int) -> bool:
# Helper function to check if a number is prime
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# Calculate the integer square root of n
k = int(n**0.5)
# Check if n is greater than 3, if k squared is n, and if k is prime
if n > 3 and k**2 == n and is_prime(k):
return True
return False
Explore
题解中这样做的数学原理是基于如果一个数n恰好有三个正除数，那么这三个除数必须是1、k和k^2，其中k是n的一个正除数。首先计算n的平方根k是为了找到这样的一个k，然后通过检查k^2是否等于n来确定除了1和n之外，n是否只有一个独立的除数k。如果k^2 = n，那么k是n的除数，且除1和n外没有其他除数。这是因为唯一可能的除数k必须是n的平方根。
这里的逻辑是基于质数的定义，即质数除了1和自身外没有其他因数。如果k是质数且k^2 = n，那么n的因数只能是1, k, 和k^2。因为如果k是质数，它不会有除1和k本身以外的因数，所以除了1、k和k^2以外，n不可能有其他因数。这就保证了如果k是质数且k^2 = n，那么n确实只有三个因数。
is_prime函数的目的是判断一个数k是否是质数。质数的定义是只有1和它本身作为因数的正整数。函数通过从2到sqrt(k)进行循环检查，如果在这个范围内k能被任何数整除，则k不是质数。选择sqrt(k)作为循环的上界是基于数学理论：如果k有一个因数大于sqrt(k)，则另一个因数必定小于sqrt(k)。因此，只需要检测到sqrt(k)，就可以确保k没有其他因数。这样可以显著减少需要检查的因数数量，从而提高算法效率。