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

链接：762.二进制表示中质数个计算置位
难度：Easy
标签：位运算、数学
简介：给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。

题解 1 - cpp

• 编辑时间：2022-03-18
• 执行用时：48ms
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：存储质数表，遍历。

unordered_set<int> s = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
class Solution {
   public:
    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            if (s.count(getc(i))) ans++;
        }
        return ans;
    }
    int getc(int num) {
        int ans = 0;
        for (; num; num >>= 1) {
            if (num & 1) ans++;
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-04-05
• 执行用时：36ms
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            if (is_prime(cnt(i))) ans++;
        }
        return ans;
    }
    int cnt(int num) {
        int ans = 0;
        for (; num; num >>= 1) {
            if ((num & 1) == 1) ans++;
        }
        return ans;
    }
    bool is_prime(int num) {
        if (num == 0 || num == 1) return 0;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) return 0;
        }
        return 1;
    }
};