欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode】762. Prime Number of Set Bits in Binary Representation

程序员文章站 2022-07-15 12:43:09
...

题目:

【LeetCode】762. Prime Number of Set Bits in Binary Representation

题目解释:这道题的意思是要求[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;  
}