leetcode
leetcode 1701 ~ 1750
三除数

三除数

难度:

标签:

题目描述

代码结果

运行时间: 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?这样做的数学原理和逻辑是什么?
题解中这样做的数学原理是基于如果一个数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的平方根。
🦆
题解中提到如果k是质数并且k^2等于n,n才会有三个正除数。这里的逻辑是如何确保除了1, k, k^2之外不会有其他除数的?
这里的逻辑是基于质数的定义,即质数除了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是否为质数。能否详细解释这个函数的工作原理,特别是为什么它的循环范围是从2到int(math.sqrt(n)) + 1?
is_prime函数的目的是判断一个数k是否是质数。质数的定义是只有1和它本身作为因数的正整数。函数通过从2到sqrt(k)进行循环检查,如果在这个范围内k能被任何数整除,则k不是质数。选择sqrt(k)作为循环的上界是基于数学理论:如果k有一个因数大于sqrt(k),则另一个因数必定小于sqrt(k)。因此,只需要检测到sqrt(k),就可以确保k没有其他因数。这样可以显著减少需要检查的因数数量,从而提高算法效率。

相关问题