Easy

题目描述

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位个数为质数 的整数个数。

计算置位个数 就是二进制表示中 1 的个数。

  • 例如， 21 的二进制表示 10101 有 3 个计算置位。

示例 1：

输入：left = 6, right = 10
输出：4
解释：
6  -> 110 (2 个计算置位，2 是质数)
7  -> 111 (3 个计算置位，3 是质数)
8  -> 1000 (1 个计算置位，1 不是质数)
9  -> 1001 (2 个计算置位，2 是质数)
10 -> 1010 (2 个计算置位，2 是质数)
共计 4 个数字。

示例 2：

输入：left = 10, right = 15
输出：5
解释：
10 -> 1010 (2 个计算置位，2 是质数)
11 -> 1011 (3 个计算置位，3 是质数)
12 -> 1100 (2 个计算置位，2 是质数)
13 -> 1101 (3 个计算置位，3 是质数)
14 -> 1110 (3 个计算置位，3 是质数)
15 -> 1111 (4 个计算置位，4 不是质数)
共计 5 个数字。

提示：

  • 1 <= left <= right <= 10^6
  • 0 <= right - left <= 10^4

解题思路

解题思路

这道题需要统计区间内有多少个数字的二进制表示中 1 的个数是质数。

核心步骤：

  1. 遍历 [left, right] 区间内的每个数字
  2. 计算每个数字二进制表示中 1 的个数（置位个数）
  3. 判断置位个数是否为质数
  4. 统计满足条件的数字个数

关键优化：

由于题目约束 right <= 10^6，而 10^6 的二进制表示最多有 20 位，因此置位个数最多为 20。我们只需要预先计算出 20 以内的所有质数：{2, 3, 5, 7, 11, 13, 17, 19}。

计算置位个数的方法：

  • 使用内置函数 __builtin_popcount（C++）或 bin(n).count('1')（Python）
  • 或者使用位运算技巧逐个统计

判断质数的优化： 由于质数范围很小，直接用集合或位掩码预存储所有可能的质数，避免重复计算。

这种方法时间复杂度为 O(n)，其中 n 是区间长度，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        // 预存储20以内的质数，用位掩码表示
        // 2, 3, 5, 7, 11, 13, 17, 19 对应的位掩码
        int primes = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | 
                     (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19);
        
        int count = 0;
        for (int i = left; i <= right; i++) {
            int setBits = __builtin_popcount(i);
            if (primes & (1 << setBits)) {
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # 预存储20以内的质数
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        
        count = 0
        for i in range(left, right + 1):
            set_bits = bin(i).count('1')
            if set_bits in primes:
                count += 1
        return count

public class Solution {
    public int CountPrimeSetBits(int left, int right) {
        // 预存储20以内的质数，用位掩码表示
        int primes = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | 
                     (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19);
        
        int count = 0;
        for (int i = left; i <= right; i++) {
            int setBits = System.Numerics.BitOperations.PopCount((uint)i);
            if ((primes & (1 << setBits)) != 0) {
                count++;
            }
        }
        return count;
    }
}

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function(left, right) {
    // 预存储20以内的质数
    const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
    
    const countSetBits = (n) => {
        let count = 0;
        while (n) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    };
    
    let count = 0;
    for (let i = left; i <= right; i++) {
        const setBits = countSetBits(i);
        if (primes.has(setBits)) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n × log m)，其中 n = right - left + 1 是区间长度，m 是数字的最大值，log m 是计算置位个数的时间
空间复杂度O(1)，只使用了常数额外空间存储质数集合

相关题目