LWC 67: 762. Prime Number of Set Bits in Binary Representation
传送门：762. Prime Number of Set Bits in Binary Representation
Problem:
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:
- L, R will be integers L <= R in the range [1, 10^6].
- R - L will be at most 10000.
思路： 判断二进制中1的个数是否为素数，int型总共32位，所以只需要枚举出<32的素数的集合，接着非常暴力，对每个在[L, R]中的数枚举即可。
Java版本：
代码语言：javascript复制 public int countPrimeSetBits(int L, int R) {
boolean[] isPrime = new boolean[32];
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
for (int prime : primes) isPrime[prime] = true;
int ans = 0;
for (int i = L; i <= R; i) {
if (isPrime[Integer.bitCount(i)]) ans = 1;
}
return ans;
}Python版本：
代码语言：javascript复制 def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
prime = {2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31}
ans = 0
for num in range(L, R 1):
num = bin(num)
cnt = num.count('1')
if cnt in prime:
ans = 1
return ans
