762. Prime Number of Set Bits in Binary Representation #

题目 #

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

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

思路 #

代码 #

class Solution {
    public boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    public int count(int num) {
        int count = 0;
        for (int i = 30; i >= 0; i--) {
            if (((num >> i) & 1) == 1) count += 1;
        }
        return count;
    }
    public int countPrimeSetBits(int left, int right) {
        int numPrime = 0;
        for (int i = left; i <= right; i++) {
            int num = count(i);
            if (isPrime(num) == true) numPrime += 1;
        }
        return numPrime;
    }
}