题目要求
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.)
题目分析及思路
给定两个整数,找到这个区间内(包括边界值)符合要求的数字个数。要求是这个数字的二进制表示中的1的个数为奇数。求二进制形式中的1的个数可以每一位与1做与运算,然后再左移。求素数时要特别注意0和1不是素数。
python代码
class Solution:
def countPrimeSetBits(self, L: int, R: int) -> int:
count_pr_num = 0
for i in range(L, R+1):
count_bits = 0
while i:
if i & 1 != 0:
count_bits += 1
i >>= 1
count_pr = 0
for j in range(2,count_bits):
if count_bits % j == 0:
count_pr += 1
break
if count_bits == 0 or count_bits == 1:
count_pr += 1
if count_pr == 0:
count_pr_num += 1
return count_pr_num