# 762.Prime Number of Set Bits in Binary Representation

**762.Prime Number of Set Bits in Binary Representation**

难度:Easy

> 给定两个整数 L 和 R ，找到闭区间 \[L, R] 范围内，计算置位位数为质数的整数个数。

（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）

```
示例 1:

输入: L = 6, R = 10
输出: 4
解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
示例 2:

输入: L = 10, R = 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 不是质数)
注意:

L, R 是 L <= R 且在 [1, 10^6] 中的整数。
R - L 的最大值为 10000。
```

解法：用最简单的循环判断，竟然可以通过：

```
class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        int num=0;
        for(int i=L;i<=R;i++)
            if(prime.count(setnum(i)))
                num++;
        return num;
        
        
    }
private:
    unordered_set<int>prime={2,3,5,7,11,13,17,19,23,29,31};
    int setnum(int n)
    {
        int res=0;
        while(n)
        {
            if(n&1) res++;
            n=n>>1;
        }
        return res;
    }

};
```

感觉可能还有更简单的解法，因为这样的数其实有一定规律：

```
2^0 - 2^1 1
2^1 - 2^2 2
2^2 - 2^3 3
2^3 - 2^4 6
2^4 - 2^5 10
2^5 - 2^6 19
...
```

其实置位数为1的排列都是1223 2334 2334 3445...之类的排列。\
之后再看看有没有其他解法。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/762.prime_number_of_set_bits_in_binary_representation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.