762. Prime number calculation setting in binary representation

762. Prime number calculation set in binary representation

Here are two integers left and right , In the closed zone [left, right] Within the scope of , Count and return Calculate the set digit as a prime number Number of integers .

Calculate set digit In binary representation 1 The number of .

 for example , 21  The binary representation of  10101  Yes  3  A calculation set .

Example 1：

Input ：left = 6, right = 10
Output ：4
explain ：
6 -> 110 (2 A calculation set ,2 Prime number )
7 -> 111 (3 A calculation set ,3 Prime number )
9 -> 1001 (2 A calculation set ,2 Prime number )
10-> 1010 (2 A calculation set ,2 Prime number )
total 4 Calculate a number set to prime .

Example 2：

Input ：left = 10, right = 15
Output ：5
explain ：
10 -> 1010 (2 A calculation set , 2 Prime number )
11 -> 1011 (3 A calculation set , 3 Prime number )
12 -> 1100 (2 A calculation set , 2 Prime number )
13 -> 1101 (3 A calculation set , 3 Prime number )
14 -> 1110 (3 A calculation set , 3 Prime number )
15 -> 1111 (4 A calculation set , 4 Not prime )
total 5 Calculate a number set to prime .

Just use the conventional method to do this problem , Just write two functions , The solution code is as follows ：

int f(int n){
    
    int count=0;
    while(n){
    
        if(n%2==1){
    
            count++;
        }
        n=n/2;
    }
    return count;
}
bool f2(int count){
    
    if(count<=3&&count>1){
    
        return true;
    }
    if(count<=1){
    
        return false;
    }
    for(int i=2;i<=count/2;i++){
    
        if(count%i==0){
    
            return false;
        }
    }
    return true;
}

int countPrimeSetBits(int left, int right){
    
     int count=0;
     for(int i=left;i<=right;i++){
    
      
         if(f2(f(i))){
    
               count++;

         }
       
     }
     return count;

}