[leetcode] 762. Prime Number of Set Bits in Binary Representatio

[leetcode] 762. Prime Number of set bits in Binary Representatio

Description

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input:

L = 6, R = 10

Output:

4

Explanation:

6 -> 110 (2 set bits, 2 is prime)7 -> 111 (3 set bits, 3 is prime)9 -> 1001 (2 set bits , 2 is prime)10->1010 (2 set bits , 2 is prime)

Example 2:

Input:

L = 10, R = 15

Output:

5

Explanation:

10 -> 1010 (2 set bits, 2 is prime)11 -> 1011 (3 set bits, 3 is prime)12 -> 1100 (2 set bits, 2 is prime)13 -> 1101 (3 set bits, 3 is prime)14 -> 1110 (3 set bits, 3 is prime)15 -> 1111 (4 set bits, 4 is not prime)

Note:

L, R will be integers L <= R in the range [1, 10^6].R - L will be at most 10000.

分析

题目的意思是：给定一个区间[L,R]的自然数集合，然后找出每个数表示成二进制后，1的数量为质数的数量。

思路很简单，就是计算1的数量，然后判断时候是质数就行了。

代码

class Solution {public: int countPrimeSetBits(int L, int R) { int res=0; for(int i=L;i<=R;i++){ int cnt=0; for(int j=i;j>0;j>>=1){ cnt+=j&1; } if(isPrime(cnt)){ res++; } } return res; } bool isPrime(int n){ return n==2||n==3||n==5||n==7||n==11||n==13||n==17||n==19; }};

参考文献

​​762. Prime Number of Set Bits in Binary Representation​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。