传送门: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:
思路: 判断二进制中1的个数是否为素数,int型总共32位,所以只需要枚举出<32的素数的集合,接着非常暴力,对每个在[L, R]中的数枚举即可。
Java版本:
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版本:
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