Medium

题目描述

给定两个正整数 l 和 r。对于任意数字 x，除了 x 本身之外的所有正因数称为 x 的真因数。

如果一个数字恰好有 2 个真因数，则称为特殊数字。例如：

  • 数字 4 是特殊数字，因为它有真因数 1 和 2。
  • 数字 6 不是特殊数字，因为它有真因数 1、2 和 3。

返回在范围 [l, r] 内不是特殊数字的数字数量。

示例 1：

输入：l = 5, r = 7
输出：3
解释：在范围 [5, 7] 内没有特殊数字。

示例 2：

输入：l = 4, r = 16
输出：11
解释：在范围 [4, 16] 内的特殊数字是 4 和 9。

约束条件：

  • 1 <= l <= r <= 10^9

解题思路

解题思路

首先需要理解特殊数字的定义：一个数恰好有2个真因数。

通过分析可以发现，一个数有恰好2个真因数当且仅当它是质数的平方。证明如下：

  • 对于质数p的平方p²，其因数为：1, p, p²
  • 真因数（除自身外的因数）为：1, p，恰好2个
  • 对于其他数字，要么因数过少（如质数只有1个真因数），要么因数过多（如合数）

因此问题转化为：在[l, r]范围内，有多少个质数的平方？

算法步骤：

  1. 确定需要检查的质数范围：由于我们要找p²在[l, r]内的质数p，所以p的范围是[√l, √r]
  2. 使用埃拉托斯特尼筛法预处理出所有小于等于√(10^9) ≈ 31623的质数
  3. 统计在[√l, √r]范围内的质数个数，这些质数的平方就是特殊数字
  4. 返回总数字个数减去特殊数字个数

时间复杂度主要在筛质数阶段，后续统计是O(1)的。

代码实现

class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int maxSqrt = sqrt(r) + 1;
        vector<bool> isPrime(maxSqrt + 1, true);
        isPrime[0] = isPrime[1] = false;
        
        // 埃拉托斯特尼筛法
        for (int i = 2; i * i <= maxSqrt; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxSqrt; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int specialCount = 0;
        int minSqrt = ceil(sqrt(l));
        
        for (int i = minSqrt; i <= maxSqrt; i++) {
            if (isPrime[i] && (long long)i * i >= l && (long long)i * i <= r) {
                specialCount++;
            }
        }
        
        return r - l + 1 - specialCount;
    }
};

class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        import math
        
        max_sqrt = int(math.sqrt(r)) + 1
        is_prime = [True] * (max_sqrt + 1)
        is_prime[0] = is_prime[1] = False
        
        # 埃拉托斯特尼筛法
        for i in range(2, int(math.sqrt(max_sqrt)) + 1):
            if is_prime[i]:
                for j in range(i * i, max_sqrt + 1, i):
                    is_prime[j] = False
        
        special_count = 0
        min_sqrt = math.ceil(math.sqrt(l))
        
        for i in range(min_sqrt, max_sqrt + 1):
            if is_prime[i] and l <= i * i <= r:
                special_count += 1
        
        return r - l + 1 - special_count

public class Solution {
    public int NonSpecialCount(int l, int r) {
        int maxSqrt = (int)Math.Sqrt(r) + 1;
        bool[] isPrime = new bool[maxSqrt + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        // 埃拉托斯特尼筛法
        for (int i = 2; i * i <= maxSqrt; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxSqrt; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int specialCount = 0;
        int minSqrt = (int)Math.Ceiling(Math.Sqrt(l));
        
        for (int i = minSqrt; i <= maxSqrt; i++) {
            if (isPrime[i] && (long)i * i >= l && (long)i * i <= r) {
                specialCount++;
            }
        }
        
        return r - l + 1 - specialCount;
    }
}

var nonSpecialCount = function(l, r) {
    const maxSqrt = Math.floor(Math.sqrt(r)) + 1;
    const isPrime = new Array(maxSqrt + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    // 埃拉托斯特尼筛法
    for (let i = 2; i * i <= maxSqrt; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= maxSqrt; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    let specialCount = 0;
    const minSqrt = Math.ceil(Math.sqrt(l));
    
    for (let i = minSqrt; i <= maxSqrt; i++) {
        if (isPrime[i] && i * i >= l && i * i <= r) {
            specialCount++;
        }
    }
    
    return r - l + 1 - specialCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(√r log log √r)埃拉托斯特尼筛法的复杂度
空间复杂度O(√r)存储质数筛的布尔数组

相关题目