【每日一题20220802】二进制表示中质数个计算置位

兴趣爱好交流 每日一题
1

题目难度：简单
题目来源：762. 二进制表示中质数个计算置位 - 力扣（LeetCode）

描述

:mage:给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回计算置位位数为质数的整数个数。
计算置位位数就是二进制表示中 1 的个数。

  • 例如， 21的二进制表示10101有3个计算置位。

编写一个函数, 完成上述操作

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
    # your code here

示例 1：

输入：left = 6, right = 10
输出：4
解释：
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
共计 4 个计算置位为质数的数字。

示例 2：

输入：left = 10, right = 15
输出：5
解释：
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
共计 5 个计算置位为质数的数字。

提示：

  • 1 <= left <= right <= 10^6
  • 0 <= right - left <= 10^4
2

可以顺便写出自己的答案

3

我来打个样。

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # your code here
        result = 0
        for i in range(left, right+1):
            site_num = bin(i)[2:].count("1")
            if site_num > 1:
                for n in range(2, site_num):
                    if (site_num % n) == 0:
                        break
                else:
                    result += 1
        return result
1 个赞
4 
def countPrimeSetBits(self, left: int, right: int) -> int:
        res_cn = 0
        for i in range(left,right+1):
            count = bin(i).count('1')
            if count in {2,3,5,7,11,13,17,19,23,29,31}:
                res_cn += 1
        return res_cn
5 
def countPrimeSetBits(left: int, right: int) -> int:
    res_list=[str(j).count('1') for j in [bin(i) for i in range(left,right+1)] if str(j).count('1')!=1]
    n=len(res_list)
    for k in range(len(res_list)):
        for l in range(2,res_list[k]):
            if res_list[k]%l==0:
                n-=1
    return n

assert countPrimeSetBits(6,10)==4
assert countPrimeSetBits(10,15)==5