LeetCode 762.二进制表示中质数个计算置位：位运算（mask O(1)判断）

【LetMeFly】762.二进制表示中质数个计算置位：位运算（mask O(1)判断）

力扣题目链接：https://leetcode.cn/problems/prime-number-of-set-bits-in-binary-representation/

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

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

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

示例 1：

**输入：**left = 6, right = 10 **输出：**4 解释： 6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 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 <= 106
0 <= right - left <= 104

解题方法：预处理

写个脚本，计算 10 6 10^6106范围内二进制下最多有多少个1： 1 20 = 1048576 1^{20}=1048576120=1048576

再算出来其中都有哪些是质数： [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 ] [2, 3, 5, 7, 11, 13, 17, 19][2,3,5,7,11,13,17,19]

再使用一个整数二进制下的每一位代表一个数是否是质数。

1'''
2LastEditTime: 2026-02-21 12:22:44
3'''
4max_length = 0
5while 1 << max_length < 1000000:
6    max_length += 1
7print(f'max_length: {max_length}, 1 << {max_length} = {1 << max_length}')
8
9primes = []
10for i in range(2, max_length + 1):
11    isnot = False
12    for j in range(2, i):
13        if i % j == 0:
14            isnot = True
15            break
16    if not isnot:
17        primes.append(i)
18print(f'primes: {primes}')
19
20mask = 0
21for p in primes:
22    mask |= 1 << p
23print(f'mask: {mask}')
24
25"""
26max_length: 20, 1 << 20 = 1048576
27primes: [2, 3, 5, 7, 11, 13, 17, 19]
28mask: 665772
29"""
30

时间复杂度 O ( r i g h t − l e f t ) O(right - left)O(right−left)
空间复杂度 O ( N log ⁡ N ) O(N\log N)O(NlogN)

AC代码

C++

1/*
2 * @LastEditTime: 2026-02-21 12:28:09
3 */
4class Solution {
5private:
6    constexpr static int mask = 665772;
7public:
8    int countPrimeSetBits(int left, int right) {
9        int ans = 0;
10        for (int i = left; i <= right; i++) {
11            if (mask & (1 << __builtin_popcount(i))) {
12                // printf("i = %d, cnt1 = %d\n", i, __builtin_popcount(i));
13                ans++;
14            }
15        }
16        return ans;
17    }
18};
19

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

《LeetCode 762.二进制表示中质数个计算置位：位运算（mask O(1)判断）》是转载文章，点击查看原文。