【LeetCode】762. Prime Number of Set Bits in Binary Representation
程序员文章站
2022-07-15 12:43:09
...
题目:
题目解释:这道题的意思是要求[L,R]内的数,其二进制数表示时,1的个数是否为素数,若为素数则满足条件,个数+1
代码:
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;
class Solution {
public:
bool isPrime(int num){
if(num < 2)
return false;
else{
for(int i = 2; i <= sqrt(num); i++)
if(num%i == 0)
return false;
}
return true;
}
int binaryCount(int num){
int count = 0;
while(num != 0){
if(num & 1 == 1) count++;
num >>= 1;//右移一位
}
return count;
}
int countPrimeSetBits(int L, int R) {
int count = 0;
for(int num = L; num <= R; num++){
int n = binaryCount(num);
if(isPrime(n)) count++;
}
return count;
}
};
int main(){
Solution so;
int L = 10;
int R = 15;
cout << so.countPrimeSetBits(L,R) << endl;
system("pause");
return 0;
}