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.
思路:根據(jù)提示,數(shù)字范圍在1~1000000之間,而2^20 =1048576>10^6,即20位的二進(jìn)制可以表示0~1048575之間的任意數(shù),因此不用太花功夫考慮怎么判斷質(zhì)數(shù),只要找出20以內(nèi)的質(zhì)數(shù)存在集合里,判斷是否屬于集合即可(set容器的count()方法).
剩下的很簡單,對[L, R]的每個(gè)數(shù)i,每次將i和1進(jìn)行與操作
110 111
& 001 & 001
------ ------
000 001
若結(jié)果為0,則最低位為0;結(jié)果為1,則最低位為1.
然后i右移一位,繼續(xù)檢查最低位.
直到i為0.
int countPrimeSetBits(int L, int R) {
set<int> prime = {2, 3, 5, 7, 11, 13, 17, 19}; //20以內(nèi)質(zhì)數(shù)集合
int res = 0;
for (int i = L; i <= R; i++) { //遍歷從L到R的整數(shù)
int set_bits = 0; //"set bit"數(shù),即1的個(gè)數(shù)
int tmp = i;
while (tmp) {
if (tmp & 1) set_bits++; //若與操作結(jié)果為1,說明找到一個(gè)set bit
tmp >>= 1; //自右移操作
}
//檢查set_bits是否在質(zhì)數(shù)集中
if (prime.count(set_bits)) res++;
}
return res;
}
