• 注册
• 查看作者
• # 领扣：1324. Count Primes

### 1046. Prime Number of Set Bits in Binary Representation

中文English

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 `1`s 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

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)```

### Notice

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

```class Solution:
"""
@param L: an integer
@param R: an integer
@return: the count of numbers in the range [L, R] having a prime number of set bits in their binary representation
"""
def countPrimeSetBits(self, L, R):
# Write your code here
result =0
primearr = {2,3,5,7,11,13,17,19}
for number in range(L,R+1):
if bin(number).count('1') in primearr:
result=result+1
return result```

The most L and R can go is 10000, which log(10000)/log(2) is 19 something.

The set should be a {2,3,7,11,13,17,19}

Then count for binary digits, whenever a number has a prime number of '1'.

Add one to result, later just return it.

Time complexity should be O(N), which N is R-L.

Space complexity is O(1)

纽约州·纽约
• 0
• 0
• 0
• 613
• 请登录之后再进行评论

• 做任务
• 全部清空
•   