三除数
难度:
标签:
题目描述
代码结果
运行时间: 23 ms, 内存: 16.1 MB
/*
* 题目思路:
* 使用 Java Stream 流式编程来解决这个问题。我们依然需要找到 n 的所有正除数。
* 可以使用 IntStream.rangeClosed 来生成从1到n的整数,然后通过filter筛选出能整除n的数,
* 并通过count方法计数。如果计数结果是3,则返回true,否则返回false。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean isThree(int n) {
return IntStream.rangeClosed(1, n) // 生成从1到n的整数流
.filter(i -> n % i == 0) // 筛选出能整除n的数
.count() == 3; // 计数是否为3
}
}
解释
方法:
题解的核心思想是利用数学性质来判断一个数恰好有三个正除数。具体来说,一个数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)
代码细节讲解
🦆
为什么题解中首先计算n的平方根k,并检查k^2是否等于n?这样做的数学原理和逻辑是什么?
▷🦆
题解中提到如果k是质数并且k^2等于n,n才会有三个正除数。这里的逻辑是如何确保除了1, k, k^2之外不会有其他除数的?
▷🦆
题解使用了一个辅助函数is_prime来检查k是否为质数。能否详细解释这个函数的工作原理,特别是为什么它的循环范围是从2到int(math.sqrt(n)) + 1?
▷