【LeetCode-简单】762. 二进制表示中质数个计算置位（C++实现）

题目链接

762. 二进制表示中质数个计算置位

解题思路

枚举

这道题结合了判断质数和 int 转换二进制数。

对于每一个 n (∈[left, right]) ，首先计算其对应的二进制数中 1 的个数。

之后再判断质数即可。

实现代码（C++）

class Solution {
public:
    int countBinary1(int n) { // 统计n对应的2进制数中 1的个数
        int ans = 0;
        while (n != 0) {
            if (n % 2 == 1) {
                ans++;
            }
            n /= 2;
        }

        return ans;
    }

    bool zhishu(int n) { // 判断是否为质数
        cout << n << endl;
        if (n == 1) {
            return false;
        } else if (n == 2 || n == 3) {
            return true;
        } else {
            for (int i = 2; i <= sqrt(n); i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }

    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            if (zhishu(countBinary1(i))) {
                ans++;
            }
        }

        return ans;
    }
};