LeetCode---762. Prime Number of Set Bits in Binary Representation

  • 内容
  • 评论
  • 相关

分两步,首先获取为1的bit位的数量,然后判断改数量是否是质数,
10^6的位数有限,可以先写出对应范围内的质数,加快质数的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//url:https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/
class Solution {
public:
    int getSetBitNum(int n){
        int num=0;
        while(n>0){
            num++;
            n=n&(n-1);
        }
        return num;
    }
    bool isPrime(int n){
        if(0==n||1==n)
            return false;
        int i=2;
        while(i<n){
            if(0==n%i)
                return false;
            i++;
        }
        return true;
    }
 
    int countPrimeSetBits(int L, int R) {
        int num=0;
        for(int i=L;i<=R;i++){
            int n=getSetBitNum(i);
            if(isPrime(n))
                num++;
        }
        return num;
    }
};

原创文章,转载请注明: 转载自royalchen的博客

本文链接地址: LeetCode---762. Prime Number of Set Bits in Binary Representation

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注