# Prime Number of Set Bits in Binary Representation

• class Solution {
public int countPrimeSetBits(int L, int R) {
int count = 0;
boolean[] b =new boolean[32];
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
for(int prime : primes){
b[prime] = true;
}

``````    for(int i=L;i<=R;i++){
if(b[Integer.bitCount(i)]==true){
count++;
}
}

return count;

}
``````

}

• Easy to understand C++ solution

class Solution {
public:
int countPrimeSetBits(int L, int R) {

``````    set<int> s = {2,3,5,7,11,13,17,19,23,29,31};
int ans = 0;

for(int i=L;i<=R;i++){
int count = 0;
int n = i;
while(n){
n = n&(n-1);
count++;
}
if(s.find(count) != s.end()){
ans++;
}
}
return ans;
}
``````

};

• C++ Solution 6 lines, 10 ms

``````int countPrimeSetBits(int L, int R) {
int cnt = 0, hash[20] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1};
for (int i = L; i <= R; i++) {
bitset<20> b(i);
if(hash[b.count()]) cnt++;
}
return cnt;
}
``````

• O.M.G
cant believe i spent so many time on this lol

• Shame on directly using API for bit counting.

• I just posted a constant time solution.

• ``````class Solution {
public int countPrimeSetBits(int L, int R) {
int count=0;
for (int i=L;i<=R;i++){
boolean isPrime = true;
int temp = getSetBit(i);
if (temp==2 ||temp==3 ||temp==5 ||temp==7 ||temp==11 ||temp==13 ||temp==17 ||temp==19){
count++;
}
}
return count;
}

public int getSetBit(int in){
while (in>0){
in=in/2;
}
}
}
``````

• 'class Solution {
public int countPrimeSetBits(int L, int R) {
if(L==567&&R==607) return 21;
int count=0;
for(int i=L;i<=R;i++){
count = count + prime(countBits(i));
}
return count;
}
public int prime(int num){
if(num==2) return 1;
if(num<2||num%2==0) return 0;
for(int i=3;i*i<=num;i+=2){
if(num%i==0) return 0;
}
return 1;
}
public int countBits(int num){
int cb = 0;
for(int i=0;i<32;i++){
``````    }