LeetCode 762 Prime Number of Set Bits in Binary Representation 解题报告

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目要求

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

题目分析及思路

给定两个整数，找到这个区间内（包括边界值）符合要求的数字个数。要求是这个数字的二进制表示中的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