問題（Easy）：

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:
Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)

Example 2:
Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

Note:

1. L, R will be integers L <= R in the range [1, 10^6].
2. R - L will be at most 10000.

大意：

給出兩個整數(shù)L和R，找出[L,R]（包含）范圍中的數(shù)字以二進(jìn)制表示時所擁有的比特位為1的數(shù)量為質(zhì)數(shù)的總個數(shù)。

（比如，21寫成二進(jìn)制為10101，有三個比特位為1。此外，1不是質(zhì)數(shù)。）

例1：
輸入：L = 6, R = 10
輸出：4
解釋：
6 -> 110 (2 個1, 2 是質(zhì)數(shù))
7 -> 111 (3 個1, 3 是質(zhì)數(shù))
9 -> 1001 (2 個1 , 2 是質(zhì)數(shù))
10->1010 (2 個1 , 2 是質(zhì)數(shù))

例2：
輸入：L = 10, R = 15
輸出：5
10 -> 1010 (2 個1, 2 是質(zhì)數(shù))
11 -> 1011 (3 個1, 3 是質(zhì)數(shù))
12 -> 1100 (2 個1, 2 是質(zhì)數(shù))
13 -> 1101 (3 個1, 3 是質(zhì)數(shù))
14 -> 1110 (3 個1, 3 是質(zhì)數(shù))
15 -> 1111 (4 個1, 4 不是質(zhì)數(shù))

注意：

1. L、R會是[1,10^6]范圍內(nèi)的整數(shù)。
2. R - L最多為10000。

思路：

沒有特別簡單的方法，只能對于范圍內(nèi)每個數(shù)字去數(shù)其二進(jìn)制表示形式下有幾個1，這一點可以通過右移操作來一位位判斷。然后對于1的個數(shù)，判斷其是否是質(zhì)數(shù)，因為R最多為10^6，所以最大的數(shù)字轉(zhuǎn)換成二進(jìn)制是20位，也就是最多有二十個1，那么只需要知道1~20有哪些質(zhì)數(shù)就可以了，并不多，只有2、3、5、7、11、13、17、19，可以發(fā)現(xiàn)剩下的數(shù)字除了1以外都能被2或者3整除，所以可以直接判斷了。

代碼（C++）：

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        int res = 0;
        for (int i = L; i <= R; i++) {
            int num = 0;
            int temp = i;
            while (temp > 0) {
                if (temp & 1 == 1) num++;
                temp = temp >> 1;
            }
            
            if (num == 2 || num == 3) res++;
            else if (num != 1 && num % 2 !=0 && num % 3 != 0) res++;
        }
        return res;
    }
};

當(dāng)然，判斷質(zhì)數(shù)的時候可以用set來判斷，可能會更快一些。

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        set<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19 };
        int res = 0;
        for (int i = L; i <= R; i++) {
            int num = 0;
            int temp = i;
            while (temp > 0) {
                if (temp & 1 == 1) num++;
                temp = temp >> 1;
            }
            
            res += primes.count(num);
        }
        return res;
    }
};

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首頁